# 算法设计：金矿问题解析和代码实现

2021年3月11日17:50:44 发表评论 689 次浏览

## 本文概述

``````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``````

## 推荐：请在"实践首先, 在继续解决方案之前。

1. 黄金数量为正, 因此我们希望在给定约束下覆盖最大值的最大像元。
2. 在每一步中, 我们都向右侧移动了一步。因此, 我们总是最后一列。如果我们在最后一列, 那么我们将无法向右移动

## 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 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 = 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 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)