Dada una mina de oro de n*m dimensiones. Cada campo de esta mina contiene un número entero positivo que es la cantidad de oro en toneladas. Inicialmente, el minero está en la primera columna, pero puede estar en cualquier fila. Solo puede moverse (derecha->,derecha arriba /,derecha abajo\) es decir, desde una celda determinada, el minero puede moverse a la celda en diagonal hacia arriba hacia la derecha o hacia la derecha o en diagonal hacia abajo hacia la derecha. Averigüe la cantidad máxima de oro que puede recolectar.
Ejemplos:
Input : mat[][] = {{1, 3, 3},
{2, 1, 4},
{0, 6, 4}};
Output : 12
{(1,0)->(2,1)->(1,2)}
Input: mat[][] = { {1, 3, 1, 5},
{2, 2, 4, 1},
{5, 0, 2, 3},
{0, 6, 1, 2}};
Output : 16
(2,0) -> (1,1) -> (1,2) -> (0,3) OR
(2,0) -> (3,1) -> (2,2) -> (2,3)
Input : mat[][] = {{10, 33, 13, 15},
{22, 21, 04, 1},
{5, 0, 2, 3},
{0, 6, 14, 2}};
Output : 83
Fuente Entrevista Flipkart
Método 1: recursividad
Un método simple que es una implementación recursiva directa
C++
// C++ program to solve Gold Mine problem
#include<bits/stdc++.h>
using namespace std;
int collectGold(vector<vector<int>> gold, int x, int y, int n, int m) {
// Base condition.
if ((x < 0) || (x == n) || (y == m)) {
return 0;
}
// Right upper diagonal
int rightUpperDiagonal = collectGold(gold, x - 1, y + 1, n, m);
// right
int right = collectGold(gold, x, y + 1, n, m);
// Lower right diagonal
int rightLowerDiagonal = collectGold(gold, x + 1, y + 1, n, m);
// Return the maximum and store the value
return gold[x][y] + max(max(rightUpperDiagonal, rightLowerDiagonal), right);
}
int getMaxGold(vector<vector<int>> gold, int n, int m)
{
int maxGold = 0;
for (int i = 0; i < n; i++) {
// Recursive function call for ith row.
int goldCollected = collectGold(gold, i, 0, n, m);
maxGold = max(maxGold, goldCollected);
}
return maxGold;
}
// Driver Code
int main()
{
vector<vector<int>> gold { {1, 3, 1, 5},
{2, 2, 4, 1},
{5, 0, 2, 3},
{0, 6, 1, 2}
};
int m = 4, n = 4;
cout << getMaxGold(gold, n, m);
return 0;
}
Java
// Java program to solve Gold Mine problem
class GFG {
static int collectGold(int[][] gold, int x, int y,
int n, int m)
{
// Base condition.
if ((x < 0) || (x == n) || (y == m)) {
return 0;
}
// Right upper diagonal
int rightUpperDiagonal
= collectGold(gold, x - 1, y + 1, n, m);
// right
int right = collectGold(gold, x, y + 1, n, m);
// Lower right diagonal
int rightLowerDiagonal
= collectGold(gold, x + 1, y + 1, n, m);
// Return the maximum and store the value
return gold[x][y]
+ Math.max(Math.max(rightUpperDiagonal,
rightLowerDiagonal),
right);
}
static int getMaxGold(int[][] gold, int n, int m)
{
int maxGold = 0;
for (int i = 0; i < n; i++) {
// Recursive function call for ith row.
int goldCollected
= collectGold(gold, i, 0, n, m);
maxGold = Math.max(maxGold, goldCollected);
}
return maxGold;
}
public static void main(String[] args)
{
int[][] gold = { { 1, 3, 1, 5 },
{ 2, 2, 4, 1 },
{ 5, 0, 2, 3 },
{ 0, 6, 1, 2 } };
int m = 4, n = 4;
System.out.println(getMaxGold(gold, n, m));
}
}
// This code is contributed by Karandeep Singh.
Python3
# Python program to solve Gold Mine problem def collectGold(gold, x, y, n, m): # Base condition. if ((x < 0) or (x == n) or (y == m)): return 0 # Right upper diagonal rightUpperDiagonal = collectGold(gold, x - 1, y + 1, n, m) # right right = collectGold(gold, x, y + 1, n, m) # Lower right diagonal rightLowerDiagonal = collectGold(gold, x + 1, y + 1, n, m) # Return the maximum and store the value return gold[x][y] + max(max(rightUpperDiagonal, rightLowerDiagonal), right) def getMaxGold(gold,n,m): maxGold = 0 for i in range(n): # Recursive function call for ith row. goldCollected = collectGold(gold, i, 0, n, m) maxGold = max(maxGold, goldCollected) return maxGold # Driver Code gold = [[1, 3, 1, 5], [2, 2, 4, 1], [5, 0, 2, 3], [0, 6, 1, 2] ] m,n = 4,4 print(getMaxGold(gold, n, m)) # This code is contributed by shinjanpatra.
C#
// C# program to solve Gold Mine problem
using System;
public class GFG{
static public int collectGold(int[,] gold, int x,
int y, int n, int m)
{
// Base condition.
if ((x < 0) || (x == n) || (y == m)) {
return 0;
}
// Right upper diagonal
int rightUpperDiagonal = collectGold(gold, x - 1, y + 1, n, m);
// right
int right = collectGold(gold, x, y + 1, n, m);
// Lower right diagonal
int rightLowerDiagonal = collectGold(gold, x + 1, y + 1, n, m);
// Return the maximum and store the value
return gold[x,y] + Math.Max(Math.Max(rightUpperDiagonal,
rightLowerDiagonal), right);
}
static public int getMaxGold(int[,] gold, int n, int m){
int maxGold = 0;
for (int i = 0; i < n; i++) {
// Recursive function call for ith row.
int goldCollected = collectGold(gold, i, 0, n, m);
maxGold = Math.Max(maxGold, goldCollected);
}
return maxGold;
}
// Driver Code
static public void Main (){
int[,] gold = new int[,] { { 1, 3, 1, 5 },
{ 2, 2, 4, 1 },
{ 5, 0, 2, 3 },
{ 0, 6, 1, 2 } };
int m = 4, n = 4;
Console.Write(getMaxGold(gold, n, m));
}
}
// This code is contributed by shruti456rawal
Javascript
<script>
// JavaScript program to solve Gold Mine problem
function collectGold(gold,x,y,n,m) {
// Base condition.
if ((x < 0) || (x == n) || (y == m)) {
return 0;
}
// Right upper diagonal
let rightUpperDiagonal = collectGold(gold, x - 1, y + 1, n, m);
// right
let right = collectGold(gold, x, y + 1, n, m);
// Lower right diagonal
let rightLowerDiagonal = collectGold(gold, x + 1, y + 1, n, m);
// Return the maximum and store the value
return gold[x][y] + Math.max(Math.max(rightUpperDiagonal, rightLowerDiagonal), right);
}
function getMaxGold(gold,n,m)
{
maxGold = 0;
for (i = 0; i < n; i++) {
// Recursive function call for ith row.
goldCollected = collectGold(gold, i, 0, n, m);
maxGold = Math.max(maxGold, goldCollected);
}
return maxGold;
}
// Driver Code
let gold = [[1, 3, 1, 5],
[2, 2, 4, 1],
[5, 0, 2, 3],
[0, 6, 1, 2]
];
let m = 4, n = 4;
document.write(getMaxGold(gold, n, m));
// This code is contributed by shinjanpatra.
</script>
Producción
16
Complejidad del tiempo : O(3 N*M )
Espacio Auxiliar : O(N*M)
Método 2: Memoización
Enfoque ascendente: la segunda forma es tomar un espacio extra de tamaño m*n y comenzar a calcular los valores de los estados
de derecha, diagonal superior derecha y diagonal inferior derecha y guárdelo en la array 2d.
C++
// C++ program to solve Gold Mine problem
#include<bits/stdc++.h>
using namespace std;
int collectGold(vector<vector<int>> gold, int x, int y, int n, int m, vector<vector<int>> &dp) {
// Base condition.
if ((x < 0) || (x == n) || (y == m)) {
return 0;
}
if(dp[x][y] != -1){
return dp[x][y] ;
}
// Right upper diagonal
int rightUpperDiagonal = collectGold(gold, x - 1, y + 1, n, m, dp);
// right
int right = collectGold(gold, x, y + 1, n, m, dp);
// Lower right diagonal
int rightLowerDiagonal = collectGold(gold, x + 1, y + 1, n, m, dp);
// Return the maximum and store the value
return dp[x][y] = gold[x][y] + max(max(rightUpperDiagonal, rightLowerDiagonal), right);
}
int getMaxGold(vector<vector<int>> gold, int n, int m)
{
int maxGold = 0;
// Initialize the dp vector
vector<vector<int>> dp(n, vector<int>(m, -1)) ;
for (int i = 0; i < n; i++) {
// Recursive function call for ith row.
int goldCollected = collectGold(gold, i, 0, n, m, dp);
maxGold = max(maxGold, goldCollected);
}
return maxGold;
}
// Driver Code
int main()
{
vector<vector<int>> gold { {1, 3, 1, 5},
{2, 2, 4, 1},
{5, 0, 2, 3},
{0, 6, 1, 2}
};
int m = 4, n = 4;
cout << getMaxGold(gold, n, m);
return 0;
}
Java
// Java program to solve Gold Mine problem
import java.util.*;
class Gold {
static int collectGold(int[][] gold, int x, int y,
int n, int m, int[][] dp)
{
// Base condition.
if ((x < 0) || (x == n) || (y == m)) {
return 0;
}
if (dp[x][y] != -1) {
return dp[x][y];
}
// Right upper diagonal
int rightUpperDiagonal
= collectGold(gold, x - 1, y + 1, n, m, dp);
// right
int right = collectGold(gold, x, y + 1, n, m, dp);
// Lower right diagonal
int rightLowerDiagonal
= collectGold(gold, x + 1, y + 1, n, m, dp);
// Return the maximum and store the value
return gold[x][y]
+ Math.max(Math.max(rightUpperDiagonal,
rightLowerDiagonal),
right);
}
static int getMaxGold(int[][] gold, int n, int m)
{
int maxGold = 0;
int[][] dp = new int[n][m];
for (int row = 0; row < n; row++) {
Arrays.fill(dp[row], -1);
}
for (int i = 0; i < n; i++) {
// Recursive function call for ith row.
int goldCollected
= collectGold(gold, i, 0, n, m, dp);
maxGold = Math.max(maxGold, goldCollected);
}
return maxGold;
}
public static void main(String[] args)
{
int[][] gold = { { 1, 3, 1, 5 },
{ 2, 2, 4, 1 },
{ 5, 0, 2, 3 },
{ 0, 6, 1, 2 } };
int m = 4, n = 4;
System.out.println(getMaxGold(gold, n, m));
}
}
// This code is contributed by Karandeep Singh.
Python3
# Python3 program to solve Gold Mine problem def collectGold(gold, x, y, n, m, dp): # Base condition. if ((x < 0) or (x == n) or (y == m)): return 0 if(dp[x][y] != -1): return dp[x][y] # Right upper diagonal rightUpperDiagonal = collectGold(gold, x - 1, y + 1, n, m, dp) # right right = collectGold(gold, x, y + 1, n, m, dp) # Lower right diagonal rightLowerDiagonal = collectGold(gold, x + 1, y + 1, n, m, dp) # Return the maximum and store the value dp[x][y] = gold[x][y] + max(max(rightUpperDiagonal, rightLowerDiagonal), right) return dp[x][y] def getMaxGold(gold,n,m): maxGold = 0 # Initialize the dp vector dp = [[-1 for i in range(m)]for j in range(n)] for i in range(n): # Recursive function call for ith row. goldCollected = collectGold(gold, i, 0, n, m, dp) maxGold = max(maxGold, goldCollected) return maxGold # Driver Code gold = [ [1, 3, 1, 5], [2, 2, 4, 1], [5, 0, 2, 3], [0, 6, 1, 2] ] m,n = 4,4 print(getMaxGold(gold, n, m)) # This code is contributed by Shinjanpatra
C#
// C# program to solve Gold Mine problem
using System;
public class Gold
{
static int collectGold(int[,] gold, int x, int y,
int n, int m, int[,] dp)
{
// Base condition.
if ((x < 0) || (x == n) || (y == m))
{
return 0;
}
if (dp[x,y] != -1)
{
return dp[x,y];
}
// Right upper diagonal
int rightUpperDiagonal = collectGold(gold, x - 1, y + 1, n, m, dp);
// right
int right = collectGold(gold, x, y + 1, n, m, dp);
// Lower right diagonal
int rightLowerDiagonal = collectGold(gold, x + 1, y + 1, n, m, dp);
// Return the maximum and store the value
return gold[x,y] + Math.Max(Math.Max(rightUpperDiagonal,
rightLowerDiagonal), right);
}
static int getMaxGold(int[,] gold, int n, int m)
{
int maxGold = 0;
int[,] dp = new int[n, m];
for (int row = 0; row < n; row++)
{
for (int col = 0; col < m; col++)
{
dp[row,col] = -1;
}
}
for (int i = 0; i < n; i++)
{
// Recursive function call for ith row.
int goldCollected = collectGold(gold, i, 0, n, m, dp);
maxGold = Math.Max(maxGold, goldCollected);
}
return maxGold;
}
static public void Main ()
{
int[,] gold = { { 1, 3, 1, 5 },
{ 2, 2, 4, 1 },
{ 5, 0, 2, 3 },
{ 0, 6, 1, 2 } };
int m = 4, n = 4;
Console.Write(getMaxGold(gold, n, m));
}
}
// This code is contributed by kothavvsaakash
Javascript
<script>
// JavaScript program to solve Gold Mine problem
function collectGold(gold, x, y, n, m, dp)
{
// Base condition.
if ((x < 0) || (x == n) || (y == m)) {
return 0;
}
if(dp[x][y] != -1){
return dp[x][y] ;
}
// Right upper diagonal
let rightUpperDiagonal = collectGold(gold, x - 1, y + 1, n, m, dp);
// right
let right = collectGold(gold, x, y + 1, n, m, dp);
// Lower right diagonal
let rightLowerDiagonal = collectGold(gold, x + 1, y + 1, n, m, dp);
// Return the maximum and store the value
return dp[x][y] = gold[x][y] + Math.max(Math.max(rightUpperDiagonal, rightLowerDiagonal), right);
}
function getMaxGold(gold,n,m)
{
let maxGold = 0;
// Initialize the dp vector
let dp = new Array(n);
for(let i = 0; i < n; i++)
{
dp[i] = new Array(m).fill(-1);
}
for (let i = 0; i < n; i++)
{
// Recursive function call for ith row.
let goldCollected = collectGold(gold, i, 0, n, m, dp);
maxGold = Math.max(maxGold, goldCollected);
}
return maxGold;
}
// Driver Code
let gold = [ [1, 3, 1, 5],
[2, 2, 4, 1],
[5, 0, 2, 3],
[0, 6, 1, 2] ];
let m = 4, n = 4;
document.write(getMaxGold(gold, n, m));
// This code is contributed by Shinjanpatra
</script>
Producción
16
Tiempo Complejidad : O(m*n)
Complejidad espacial : O(m*n)
Método 3 : Usando Dp, Tabulación
Cree una array 2-D goldTable[][]) de la misma array mat[][]. Si observamos la pregunta de cerca, podemos notar lo siguiente.
- La cantidad de oro es positiva, por lo que nos gustaría cubrir celdas máximas de valores máximos bajo restricciones dadas.
- En cada movimiento, avanzamos un paso hacia el lado derecho. Así que siempre terminamos en la última columna. Si estamos en la última columna, entonces no podemos movernos a la derecha.
Si estamos en la primera fila o en la última columna, entonces no podemos movernos hacia arriba, así que simplemente asigne 0; de lo contrario, asigne el valor de goldTable [row-1] [col + 1] a right_up. Si estamos en la última fila o última columna, entonces no podemos movernos hacia abajo, así que simplemente asigne 0; de lo contrario, asigne el valor de goldTable [fila + 1] [col + 1] hacia arriba.
Ahora encuentra el máximo de right, right_up y right_down y luego súmalo con ese mat[row][col]. Por último, encuentre el máximo de todas las filas y la primera columna y devuélvalo.
C++
// C++ program to solve Gold Mine problem
#include<bits/stdc++.h>
using namespace std;
const int MAX = 100;
// Returns maximum amount of gold that can be collected
// when journey started from first column and moves
// allowed are right, right-up and right-down
int getMaxGold(int gold[][MAX], int m, int n)
{
// Create a table for storing intermediate results
// and initialize all cells to 0. The first row of
// goldMineTable gives the maximum gold that the miner
// can collect when starts that row
int goldTable[m][n];
memset(goldTable, 0, sizeof(goldTable));
for (int col=n-1; col>=0; col--)
{
for (int row=0; row<m; row++)
{
// Gold collected on going to the cell on the right(->)
int right = (col==n-1)? 0: goldTable[row][col+1];
// Gold collected on going to the cell to right up (/)
int right_up = (row==0 || col==n-1)? 0:
goldTable[row-1][col+1];
// Gold collected on going to the cell to right down (\)
int right_down = (row==m-1 || col==n-1)? 0:
goldTable[row+1][col+1];
// Max gold collected from taking either of the
// above 3 paths
goldTable[row][col] = gold[row][col] +
max(right, max(right_up, right_down));
}
}
// The max amount of gold collected will be the max
// value in first column of all rows
int res = goldTable[0][0];
for (int i=1; i<m; i++)
res = max(res, goldTable[i][0]);
return res;
}
// Driver Code
int main()
{
int gold[MAX][MAX]= { {1, 3, 1, 5},
{2, 2, 4, 1},
{5, 0, 2, 3},
{0, 6, 1, 2}
};
int m = 4, n = 4;
cout << getMaxGold(gold, m, n);
return 0;
}
Java
// Java program to solve Gold Mine problem
import java.util.Arrays;
class GFG {
static final int MAX = 100;
// Returns maximum amount of gold that
// can be collected when journey started
// from first column and moves allowed
// are right, right-up and right-down
static int getMaxGold(int gold[][],
int m, int n)
{
// Create a table for storing
// intermediate results and initialize
// all cells to 0. The first row of
// goldMineTable gives the maximum
// gold that the miner can collect
// when starts that row
int goldTable[][] = new int[m][n];
for(int[] rows:goldTable)
Arrays.fill(rows, 0);
for (int col = n-1; col >= 0; col--)
{
for (int row = 0; row < m; row++)
{
// Gold collected on going to
// the cell on the right(->)
int right = (col == n-1) ? 0
: goldTable[row][col+1];
// Gold collected on going to
// the cell to right up (/)
int right_up = (row == 0 ||
col == n-1) ? 0 :
goldTable[row-1][col+1];
// Gold collected on going to
// the cell to right down (\)
int right_down = (row == m-1
|| col == n-1) ? 0 :
goldTable[row+1][col+1];
// Max gold collected from taking
// either of the above 3 paths
goldTable[row][col] = gold[row][col]
+ Math.max(right, Math.max(right_up,
right_down));
}
}
// The max amount of gold collected will be
// the max value in first column of all rows
int res = goldTable[0][0];
for (int i = 1; i < m; i++)
res = Math.max(res, goldTable[i][0]);
return res;
}
//driver code
public static void main(String arg[])
{
int gold[][]= { {1, 3, 1, 5},
{2, 2, 4, 1},
{5, 0, 2, 3},
{0, 6, 1, 2} };
int m = 4, n = 4;
System.out.print(getMaxGold(gold, m, n));
}
}
// This code is contributed by Anant Agarwal.
Python3
# Python program to solve # Gold Mine problem MAX = 100 # Returns maximum amount of # gold that can be collected # when journey started from # first column and moves # allowed are right, right-up # and right-down def getMaxGold(gold, m, n): # Create a table for storing # intermediate results # and initialize all cells to 0. # The first row of # goldMineTable gives the # maximum gold that the miner # can collect when starts that row goldTable = [[0 for i in range(n)] for j in range(m)] for col in range(n-1, -1, -1): for row in range(m): # Gold collected on going to # the cell on the right(->) if (col == n-1): right = 0 else: right = goldTable[row][col+1] # Gold collected on going to # the cell to right up (/) if (row == 0 or col == n-1): right_up = 0 else: right_up = goldTable[row-1][col+1] # Gold collected on going to # the cell to right down (\) if (row == m-1 or col == n-1): right_down = 0 else: right_down = goldTable[row+1][col+1] # Max gold collected from taking # either of the above 3 paths goldTable[row][col] = gold[row][col] + max(right, right_up, right_down) # The max amount of gold # collected will be the max # value in first column of all rows res = goldTable[0][0] for i in range(1, m): res = max(res, goldTable[i][0]) return res # Driver code gold = [[1, 3, 1, 5], [2, 2, 4, 1], [5, 0, 2, 3], [0, 6, 1, 2]] m = 4 n = 4 print(getMaxGold(gold, m, n)) # This code is contributed # by Soumen Ghosh.
C#
// C# program to solve Gold Mine problem
using System;
class GFG
{
static int MAX = 100;
// Returns maximum amount of gold that
// can be collected when journey started
// from first column and moves allowed are
// right, right-up and right-down
static int getMaxGold(int[,] gold,
int m, int n)
{
// Create a table for storing intermediate
// results and initialize all cells to 0.
// The first row of goldMineTable gives
// the maximum gold that the miner
// can collect when starts that row
int[,] goldTable = new int[m, n];
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
goldTable[i, j] = 0;
for (int col = n - 1; col >= 0; col--)
{
for (int row = 0; row < m; row++)
{
// Gold collected on going to
// the cell on the right(->)
int right = (col == n - 1) ? 0 :
goldTable[row, col + 1];
// Gold collected on going to
// the cell to right up (/)
int right_up = (row == 0 || col == n - 1)
? 0 : goldTable[row-1,col+1];
// Gold collected on going
// to the cell to right down (\)
int right_down = (row == m - 1 || col == n - 1)
? 0 : goldTable[row + 1, col + 1];
// Max gold collected from taking
// either of the above 3 paths
goldTable[row, col] = gold[row, col] +
Math.Max(right, Math.Max(right_up,
right_down));
}
}
// The max amount of gold collected will be the max
// value in first column of all rows
int res = goldTable[0, 0];
for (int i = 1; i < m; i++)
res = Math.Max(res, goldTable[i, 0]);
return res;
}
// Driver Code
static void Main()
{
int[,] gold = new int[,]{{1, 3, 1, 5},
{2, 2, 4, 1},
{5, 0, 2, 3},
{0, 6, 1, 2}
};
int m = 4, n = 4;
Console.Write(getMaxGold(gold, m, n));
}
}
// This code is contributed by DrRoot_
PHP
<?php
// Php program to solve Gold Mine problem
// Returns maximum amount of gold that
// can be collected when journey started
// from first column and moves allowed are
// right, right-up and right-down
function getMaxGold($gold, $m, $n)
{
$MAX = 100 ;
// Create a table for storing intermediate
// results and initialize all cells to 0.
// The first row of goldMineTable gives the
// maximum gold that the miner can collect
// when starts that row
$goldTable = array(array());
for ($i = 0; $i < $m ; $i ++)
for($j = 0; $j < $n ; $j ++)
$goldTable[$i][$j] = 0 ;
for ($col = $n - 1; $col >= 0 ; $col--)
{
for ($row = 0 ; $row < $m ; $row++)
{
// Gold collected on going to
// the cell on the right(->)
if ($col == $n - 1)
$right = 0 ;
else
$right = $goldTable[$row][$col + 1];
// Gold collected on going to
// the cell to right up (/)
if ($row == 0 or $col == $n - 1)
$right_up = 0 ;
else
$right_up = $goldTable[$row - 1][$col + 1];
// Gold collected on going to
// the cell to right down (\)
if ($row == $m - 1 or $col == $n - 1)
$right_down = 0 ;
else
$right_down = $goldTable[$row + 1][$col + 1];
// Max gold collected from taking
// either of the above 3 paths
$goldTable[$row][$col] = $gold[$row][$col] +
max($right, $right_up,
$right_down);
}
}
// The max amount of gold collected will be the
// max value in first column of all rows
$res = $goldTable[0][0] ;
for ($i = 0; $i < $m; $i++)
$res = max($res, $goldTable[$i][0]);
return $res;
}
// Driver code
$gold = array(array(1, 3, 1, 5),
array(2, 2, 4, 1),
array(5, 0, 2, 3),
array(0, 6, 1, 2));
$m = 4 ;
$n = 4 ;
echo getMaxGold($gold, $m, $n) ;
// This code is contributed by Ryuga
?>
Javascript
<script>
// JavaScript program to solve Gold Mine problem
let MAX = 100;
// Returns maximum amount of gold that
// can be collected when journey started
// from first column and moves allowed
// are right, right-up and right-down
function getMaxGold(gold, m, n)
{
// Create a table for storing
// intermediate results and initialize
// all cells to 0. The first row of
// goldMineTable gives the maximum
// gold that the miner can collect
// when starts that row
let goldTable = new Array(m);
for(let i = 0; i < m; i++)
{
goldTable[i] = new Array(n);
for(let j = 0; j < n; j++)
{
goldTable[i][j] = 0;
}
}
for (let col = n-1; col >= 0; col--)
{
for (let row = 0; row < m; row++)
{
// Gold collected on going to
// the cell on the right(->)
let right = (col == n-1) ? 0
: goldTable[row][col+1];
// Gold collected on going to
// the cell to right up (/)
let right_up = (row == 0 ||
col == n-1) ? 0 :
goldTable[row-1][col+1];
// Gold collected on going to
// the cell to right down (\)
let right_down = (row == m-1
|| col == n-1) ? 0 :
goldTable[row+1][col+1];
// Max gold collected from taking
// either of the above 3 paths
goldTable[row][col] = gold[row][col]
+ Math.max(right, Math.max(right_up,
right_down));
}
}
// The max amount of gold collected will be
// the max value in first column of all rows
let res = goldTable[0][0];
for (let i = 1; i < m; i++)
res = Math.max(res, goldTable[i][0]);
return res;
}
let gold = [ [1, 3, 1, 5],
[2, 2, 4, 1],
[5, 0, 2, 3],
[0, 6, 1, 2] ];
let m = 4, n = 4;
document.write(getMaxGold(gold, m, n));
</script>
Producción
16
Complejidad de tiempo: O(m*n)
Complejidad de espacio: O(m*n) Rakesh Kumar
contribuye con este artículo . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA