# Gold Mine Problem

The Gold Mine Problem is a classic dynamic programming problem where we are given a 2D matrix representing a gold mine. Each cell in the matrix contains a certain amount of gold. The objective is to find the maximum amount of gold that can be collected by starting at any column of the first row and moving only right, right-up, or right-down in subsequent columns until reaching the last column. In this article, we will explain the problem statement and provide a Java solution using dynamic programming.

## Problem Statement:

Given a 2D matrix representing a gold mine, we need to find the maximum amount of gold that can be collected by starting at any column of the first row and moving only right, right-up, or right-down in subsequent columns until reaching the last column.

## Code Solution:

To solve this problem efficiently, we can use dynamic programming. The idea is to calculate the maximum amount of gold that can be collected at each cell in the matrix by considering the maximum amount of gold that can be collected from the neighboring cells in the previous column. We will iterate column-wise from left to right, updating the values in the matrix.

``````// Java Program
// Gold Mine Problem
public class GoldMineProblem
{
public void maxGold(int[][] goldMine)
{
int row = goldMine.length;
int col = goldMine[0].length;
int max = 0;
for (int i = 1; i < col; ++i)
{
for (int j = 0; j < row; ++j)
{
max = Integer.MIN_VALUE;
if (goldMine[j][i - 1] + goldMine[j][i] > max)
{
// Left
max = goldMine[j][i - 1] + goldMine[j][i];
}
if (j - 1 >= 0 && goldMine[j - 1][i - 1] + goldMine[j][i] > max)
{
// Top Left
max = goldMine[j - 1][i - 1] + goldMine[j][i];
}
if (j + 1 < row && goldMine[j + 1][i - 1] + goldMine[j][i] > max)
{
// Botoom Left
max = goldMine[j + 1][i - 1] + goldMine[j][i];
}
goldMine[j][i] = max;
}
}
// Check result in last column
max = goldMine[0][col - 1];
for (int i = 1; i < row; ++i)
{
if (max < goldMine[i][col - 1])
{
max = goldMine[i][col - 1];
}
}
System.out.println(max);
}
public static void main(String[] args)
{
int[][] matrix = {
{
14 , 5 , 6 , 9 , 3
},
{
12 , 9 , 7 , 10 , 2
},
{
15 , 6 , 8 , 3 , 1
},
{
13 , 8 , 9 , 4 , 2
}
};
// [15 + 9 + 8 + 10 + 3] = 45
}
}``````

#### Output

``45``
``````// Include header file
#include <iostream>
#include <vector>
#include <limits.h>

using namespace std;
// C++ Program
// Gold Mine Problem
class GoldMineProblem
{
public: void maxGold(vector < vector < int >> goldMine)
{
int row = goldMine.size();
int col = goldMine[0].size();
int max = 0;
for (int i = 1; i < col; ++i)
{
for (int j = 0; j < row; ++j)
{
max = INT_MIN;
if (goldMine[j][i - 1] + goldMine[j][i] > max)
{
// Left
max = goldMine[j][i - 1] + goldMine[j][i];
}
if (j - 1 >= 0 && goldMine[j - 1][i - 1] + goldMine[j][i] > max)
{
// Top Left
max = goldMine[j - 1][i - 1] + goldMine[j][i];
}
if (j + 1 < row && goldMine[j + 1][i - 1] + goldMine[j][i] > max)
{
// Botoom Left
max = goldMine[j + 1][i - 1] + goldMine[j][i];
}
goldMine[j][i] = max;
}
}
// Check result in last column
max = goldMine[0][col - 1];
for (int i = 1; i < row; ++i)
{
if (max < goldMine[i][col - 1])
{
max = goldMine[i][col - 1];
}
}
cout << max << endl;
}
};
int main()
{
vector < vector < int >> matrix
{
{
14 , 5 , 6 , 9 , 3
} , {
12 , 9 , 7 , 10 , 2
} , {
15 , 6 , 8 , 3 , 1
} , {
13 , 8 , 9 , 4 , 2
}
};
// [15 + 9 + 8 + 10 + 3] = 45
return 0;
}``````

#### Output

``45``
``````// Include namespace system
using System;
// Csharp Program
// Gold Mine Problem
public class GoldMineProblem
{
public void maxGold(int[,] goldMine)
{
int row = goldMine.GetLength(0);
int col = goldMine.GetLength(1);
int max = 0;
for (int i = 1; i < col; ++i)
{
for (int j = 0; j < row; ++j)
{
max = int.MinValue;
if (goldMine[j,i - 1] + goldMine[j,i] > max)
{
// Left
max = goldMine[j,i - 1] + goldMine[j,i];
}
if (j - 1 >= 0 && goldMine[j - 1,i - 1] + goldMine[j,i] > max)
{
// Top Left
max = goldMine[j - 1,i - 1] + goldMine[j,i];
}
if (j + 1 < row && goldMine[j + 1,i - 1] + goldMine[j,i] > max)
{
// Botoom Left
max = goldMine[j + 1,i - 1] + goldMine[j,i];
}
goldMine[j,i] = max;
}
}
// Check result in last column
max = goldMine[0,col - 1];
for (int i = 1; i < row; ++i)
{
if (max < goldMine[i,col - 1])
{
max = goldMine[i,col - 1];
}
}
Console.WriteLine(max);
}
public static void Main(String[] args)
{
int[,] matrix = {
{
14 , 5 , 6 , 9 , 3
},
{
12 , 9 , 7 , 10 , 2
},
{
15 , 6 , 8 , 3 , 1
},
{
13 , 8 , 9 , 4 , 2
}
};
// [15 + 9 + 8 + 10 + 3] = 45
}
}``````

#### Output

``45``
``````package main
import "math"
import "fmt"
// Go Program
// Gold Mine Problem
type GoldMineProblem struct {}
func getGoldMineProblem() * GoldMineProblem {
var me *GoldMineProblem = &GoldMineProblem {}
return me
}
func(this GoldMineProblem) maxGold(goldMine[][] int) {
var row int = len(goldMine)
var col int = len(goldMine[0])
var max int = 0
for i := 1 ; i < col ; i++ {
for j := 0 ; j < row ; j++ {
max = math.MinInt64
if goldMine[j][i - 1] + goldMine[j][i] > max {
// Left
max = goldMine[j][i - 1] + goldMine[j][i]
}
if j - 1 >= 0 && goldMine[j - 1][i - 1] + goldMine[j][i] > max {
// Top Left
max = goldMine[j - 1][i - 1] + goldMine[j][i]
}
if j + 1 < row && goldMine[j + 1][i - 1] + goldMine[j][i] > max {
// Botoom Left
max = goldMine[j + 1][i - 1] + goldMine[j][i]
}
goldMine[j][i] = max
}
}
// Check result in last column
max = goldMine[0][col - 1]
for i := 1 ; i < row ; i++ {
if max < goldMine[i][col - 1] {
max = goldMine[i][col - 1]
}
}
fmt.Println(max)
}
func main() {
var task * GoldMineProblem = getGoldMineProblem()
var matrix = [][] int   {
{ 14 , 5 , 6 , 9 , 3 },
{ 12 , 9 , 7 , 10 , 2 },
{ 15 , 6 , 8 , 3 , 1 },
{ 13 , 8 , 9 , 4 , 2 },
}
// [15 + 9 + 8 + 10 + 3] = 45
}``````

#### Output

``45``
``````<?php
// Php Program
// Gold Mine Problem
class GoldMineProblem
{
public	function maxGold(\$goldMine)
{
\$row = count(\$goldMine);
\$col = count(\$goldMine[0]);
\$max = 0;
for (\$i = 1; \$i < \$col; ++\$i)
{
for (\$j = 0; \$j < \$row; ++\$j)
{
\$max = -PHP_INT_MAX;
if (\$goldMine[\$j][\$i - 1] + \$goldMine[\$j][\$i] > \$max)
{
// Left
\$max = \$goldMine[\$j][\$i - 1] + \$goldMine[\$j][\$i];
}
if (\$j - 1 >= 0 && \$goldMine[\$j - 1][\$i - 1] +
\$goldMine[\$j][\$i] > \$max)
{
// Top Left
\$max = \$goldMine[\$j - 1][\$i - 1] + \$goldMine[\$j][\$i];
}
if (\$j + 1 < \$row && \$goldMine[\$j + 1][\$i - 1] +
\$goldMine[\$j][\$i] > \$max)
{
// Botoom Left
\$max = \$goldMine[\$j + 1][\$i - 1] + \$goldMine[\$j][\$i];
}
\$goldMine[\$j][\$i] = \$max;
}
}
// Check result in last column
\$max = \$goldMine[0][\$col - 1];
for (\$i = 1; \$i < \$row; ++\$i)
{
if (\$max < \$goldMine[\$i][\$col - 1])
{
\$max = \$goldMine[\$i][\$col - 1];
}
}
echo(\$max.
"\n");
}
}

function main()
{
\$matrix = array(
array(14, 5, 6, 9, 3),
array(12, 9, 7, 10, 2),
array(15, 6, 8, 3, 1),
array(13, 8, 9, 4, 2)
);
// [15 + 9 + 8 + 10 + 3] = 45
}
main();``````

#### Output

``45``
``````// Node JS Program
// Gold Mine Problem
class GoldMineProblem
{
maxGold(goldMine)
{
var row = goldMine.length;
var col = goldMine[0].length;
var max = 0;
for (var i = 1; i < col; ++i)
{
for (var j = 0; j < row; ++j)
{
max = -Number.MAX_VALUE;
if (goldMine[j][i - 1] + goldMine[j][i] > max)
{
// Left
max = goldMine[j][i - 1] + goldMine[j][i];
}
if (j - 1 >= 0 && goldMine[j - 1][i - 1] + goldMine[j][i] > max)
{
// Top Left
max = goldMine[j - 1][i - 1] + goldMine[j][i];
}
if (j + 1 < row && goldMine[j + 1][i - 1] + goldMine[j][i] > max)
{
// Botoom Left
max = goldMine[j + 1][i - 1] + goldMine[j][i];
}
goldMine[j][i] = max;
}
}
// Check result in last column
max = goldMine[0][col - 1];
for (var i = 1; i < row; ++i)
{
if (max < goldMine[i][col - 1])
{
max = goldMine[i][col - 1];
}
}
console.log(max);
}
}

function main()
{
var matrix = [
[14, 5, 6, 9, 3],
[12, 9, 7, 10, 2],
[15, 6, 8, 3, 1],
[13, 8, 9, 4, 2]
];
// [15 + 9 + 8 + 10 + 3] = 45
}
main();``````

#### Output

``45``
``````import sys
#  Python 3 Program
#  Gold Mine Problem
class GoldMineProblem :
def maxGold(self, goldMine) :
row = len(goldMine)
col = len(goldMine[0])
max = 0
i = 1
while (i < col) :
j = 0
while (j < row) :
max = -sys.maxsize
if (goldMine[j][i - 1] + goldMine[j][i] > max) :
#  Left
max = goldMine[j][i - 1] + goldMine[j][i]

if (j - 1 >= 0 and goldMine[j - 1][i - 1] +
goldMine[j][i] > max) :
#  Top Left
max = goldMine[j - 1][i - 1] + goldMine[j][i]

if (j + 1 < row and goldMine[j + 1][i - 1] +
goldMine[j][i] > max) :
#  Botoom Left
max = goldMine[j + 1][i - 1] + goldMine[j][i]

goldMine[j][i] = max
j += 1

i += 1

#  Check result in last column
max = goldMine[0][col - 1]
i = 1
while (i < row) :
if (max < goldMine[i][col - 1]) :
max = goldMine[i][col - 1]

i += 1

print(max)

def main() :
matrix = [
[14, 5, 6, 9, 3],
[12, 9, 7, 10, 2],
[15, 6, 8, 3, 1],
[13, 8, 9, 4, 2]
]
#  [15 + 9 + 8 + 10 + 3] = 45

if __name__ == "__main__": main()``````

#### Output

``45``
``````#  Ruby Program
#  Gold Mine Problem
class GoldMineProblem
def maxGold(goldMine)
row = goldMine.length
col = goldMine[0].length
max = 0
i = 1
while (i < col)
j = 0
while (j < row)
max = -(2 ** (0. size * 8 - 2))
if (goldMine[j][i - 1] + goldMine[j][i] > max)
#  Left
max = goldMine[j][i - 1] + goldMine[j][i]
end

if (j - 1 >= 0 && goldMine[j - 1][i - 1] +
goldMine[j][i] > max)
#  Top Left
max = goldMine[j - 1][i - 1] + goldMine[j][i]
end

if (j + 1 < row && goldMine[j + 1][i - 1] +
goldMine[j][i] > max)
#  Botoom Left
max = goldMine[j + 1][i - 1] + goldMine[j][i]
end

goldMine[j][i] = max
j += 1
end

i += 1
end

#  Check result in last column
max = goldMine[0][col - 1]
i = 1
while (i < row)
if (max < goldMine[i][col - 1])
max = goldMine[i][col - 1]
end

i += 1
end

print(max, "\n")
end

end

def main()
matrix = [
[14, 5, 6, 9, 3],
[12, 9, 7, 10, 2],
[15, 6, 8, 3, 1],
[13, 8, 9, 4, 2]
]
#  [15 + 9 + 8 + 10 + 3] = 45
end

main()``````

#### Output

``````45
``````
``````// Scala Program
// Gold Mine Problem
class GoldMineProblem()
{
def maxGold(goldMine: Array[Array[Int]]): Unit = {
var row: Int = goldMine.length;
var col: Int = goldMine(0).length;
var max: Int = 0;
var i: Int = 1;
while (i < col)
{
var j: Int = 0;
while (j < row)
{
max = Int.MinValue;
if (goldMine(j)(i - 1) + goldMine(j)(i) > max)
{
// Left
max = goldMine(j)(i - 1) + goldMine(j)(i);
}
if (j - 1 >= 0 && goldMine(j - 1)(i - 1) +
goldMine(j)(i) > max)
{
// Top Left
max = goldMine(j - 1)(i - 1) + goldMine(j)(i);
}
if (j + 1 < row && goldMine(j + 1)(i - 1) +
goldMine(j)(i) > max)
{
// Botoom Left
max = goldMine(j + 1)(i - 1) + goldMine(j)(i);
}
goldMine(j)(i) = max;
j += 1;
}
i += 1;
}
// Check result in last column
max = goldMine(0)(col - 1);
i = 1;
while (i < row)
{
if (max < goldMine(i)(col - 1))
{
max = goldMine(i)(col - 1);
}
i += 1;
}
println(max);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: GoldMineProblem = new GoldMineProblem();
var matrix: Array[Array[Int]] = Array(
Array(14, 5, 6, 9, 3),
Array(12, 9, 7, 10, 2),
Array(15, 6, 8, 3, 1),
Array(13, 8, 9, 4, 2)
);
// [15 + 9 + 8 + 10 + 3] = 45
}
}``````

#### Output

``45``
``````import Foundation;
// Swift 4 Program
// Gold Mine Problem
class GoldMineProblem
{
func maxGold(_ goldMine: inout[[Int]])
{
let row: Int = goldMine.count;
let col: Int = goldMine[0].count;
var max: Int = 0;
var i: Int = 1;
while (i < col)
{
var j: Int = 0;
while (j < row)
{
max = Int.min;
if (goldMine[j][i - 1] + goldMine[j][i] > max)
{
// Left
max = goldMine[j][i - 1] + goldMine[j][i];
}
if (j - 1 >= 0 && goldMine[j - 1][i - 1] +
goldMine[j][i] > max)
{
// Top Left
max = goldMine[j - 1][i - 1] + goldMine[j][i];
}
if (j + 1 < row && goldMine[j + 1][i - 1] +
goldMine[j][i] > max)
{
// Botoom Left
max = goldMine[j + 1][i - 1] + goldMine[j][i];
}
goldMine[j][i] = max;
j += 1;
}
i += 1;
}
// Check result in last column
max = goldMine[0][col - 1];
i = 1;
while (i < row)
{
if (max < goldMine[i][col - 1])
{
max = goldMine[i][col - 1];
}
i += 1;
}
print(max);
}
}
func main()
{
var matrix: [[Int]] = [
[14, 5, 6, 9, 3],
[12, 9, 7, 10, 2],
[15, 6, 8, 3, 1],
[13, 8, 9, 4, 2]
];
// [15 + 9 + 8 + 10 + 3] = 45
}
main();``````

#### Output

``45``
``````// Kotlin Program
// Gold Mine Problem
class GoldMineProblem
{
fun maxGold(goldMine: Array < Array < Int >> ): Unit
{
val row: Int = goldMine.count();
val col: Int = goldMine[0].count();
var max: Int;
var i: Int = 1;
while (i < col)
{
var j: Int = 0;
while (j < row)
{
max = Int.MIN_VALUE;
if (goldMine[j][i - 1] + goldMine[j][i] > max)
{
// Left
max = goldMine[j][i - 1] + goldMine[j][i];
}
if (j - 1 >= 0 && goldMine[j - 1][i - 1] +
goldMine[j][i] > max)
{
// Top Left
max = goldMine[j - 1][i - 1] + goldMine[j][i];
}
if (j + 1 < row && goldMine[j + 1][i - 1] +
goldMine[j][i] > max)
{
// Botoom Left
max = goldMine[j + 1][i - 1] + goldMine[j][i];
}
goldMine[j][i] = max;
j += 1;
}
i += 1;
}
// Check result in last column
max = goldMine[0][col - 1];
i = 1;
while (i < row)
{
if (max < goldMine[i][col - 1])
{
max = goldMine[i][col - 1];
}
i += 1;
}
println(max);
}
}
fun main(args: Array < String > ): Unit
{
val matrix: Array < Array < Int >> = arrayOf(
arrayOf(14, 5, 6, 9, 3),
arrayOf(12, 9, 7, 10, 2),
arrayOf(15, 6, 8, 3, 1),
arrayOf(13, 8, 9, 4, 2)
);
// [15 + 9 + 8 + 10 + 3] = 45
}``````

#### Output

``45``

## Explanation:

1. We start by defining the `maxGold` method that takes a 2D array `goldMine` as input. This method will calculate and output the maximum amount of gold that can be collected.

2. We retrieve the number of rows and columns in the `goldMine` matrix using `goldMine.length` and `goldMine[0].length`, respectively.

3. We initialize a variable `max` to store the maximum amount of gold.

4. We iterate column-wise from the second column (index `1`) to the last column. Inside this loop, we iterate row-wise.

5. For each cell, we initialize `max` to `Integer.MIN_VALUE`, which is the smallest possible integer value. This ensures that any gold amount will be greater than the initial value of `max`.

6. We consider three possible paths to reach the current cell: from the left, top-left, or bottom-left cell.

7. We compare the sum of the gold amount in the previous column's cell and the current cell with the current maximum (`max`). If it is greater, we update `max` accordingly.

8. Similarly, we check the top-left and bottom-left cells if they exist and update `max` if the sum of their gold amounts and the current cell's gold amount is greater.

9. Once we have determined the maximum amount of gold that can be collected at the current cell, we update the value of that cell in the `goldMine` matrix.

10. After completing the column-wise iteration, we need to find the maximum value in the last column. We initialize `max` with the value of the first cell in the last column.

11. We iterate over the remaining cells in the last column and update `max` if a larger value is found.

12. Finally, we output the value of `max`, which represents the maximum amount of gold that can be collected.

## Example Output:

In the given example, the maximum amount of gold that can be collected is 45. The path that yields this maximum value is [15, 9, 8, 10, 3].

The Gold Mine Problem can be efficiently solved using dynamic programming techniques. By breaking down the problem into subproblems and calculating the maximum amount of gold at each cell, we can find the overall maximum amount of gold that can be collected. The Java implementation provided in this article demonstrates the step-by-step process of solving the problem. By understanding the problem statement and the corresponding solution, you can apply similar techniques to solve other dynamic programming problems efficiently.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.