本文概述给定一个n * m尺寸的金矿。该矿场中的每个字段都包含一个正整数, 该整数是黄金的吨数。最初, 矿工位于第一列, 但可以位于任何行。他只能从给定单元移动(右->
, 右向上/, 右向下\), 矿工可以向右或向右对角向上或向右对角向下向该单元移动。找出他可以收集的最大数量的黄金。
例子：
Input : mat[][] = {{1, 3, 3}, {2, 1, 4}, {0, 6, 4}};
Output : 12
{(1, 0)->
(2, 1)->
(2, 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资源Flipkart采访
推荐：请在"实践首先, 在继续解决方案之前。创建与给定矩阵mat [] []相同的二维矩阵goldTable [] [])。如果我们仔细观察这个问题, 我们会注意到以下情况。
- 黄金数量为正, 因此我们希望在给定约束下覆盖最大值的最大像元。
- 在每一步中, 我们都向右侧移动了一步。因此, 我们总是最后一列。如果我们在最后一列, 那么我们将无法向右移动
现在找到right, right_up和right_down的最大值, 然后将其与该mat [row] [col]相加。最后, 找到所有行和第一列的最大值并返回它。
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 problemMAX = 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 rigth(->
)
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 = 4print (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 rigth(->
)
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
?>
输出如下：
16时间复杂度：
O(m * n)
空间复杂度：
O(m * n)
【算法设计（金矿问题解析和代码实现）】如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。
推荐阅读
- JavaScript Math log()方法介绍
- 算法设计（扔鸡蛋问题 – 动态规划）
- Python MongoDB –查找数据用法介绍
- jQuery :最后一个子元素选择器用法介绍
- 优先队列（priority queue）和堆（heap）详解（二叉堆、d-堆、左式堆、斜堆和二项堆）
- vue filters过滤器的理解和使用
- vue各种属性的意义详细分析
- 运行gulp错误gulp[22202]src node_contextify.cc 626 static void
- 移动端web app开发框架MUI的使用及注意事项