Skip to main content

Goldmine problem | geeksforgeeks | dynamic programming

 Gold Mine Problem

Given a gold mine called M of (n x m) dimensions. Each field in this mine contains a positive integer which is the amount of gold in tons. Initially the miner can start from any row in the first column. From a given cell, the miner can move

  1. to the cell diagonally up towards the right 
  2. to the right
  3. to the cell diagonally down towards the right

Find out maximum amount of gold which he can collect.


Example 1:

Input: n = 3, m = 3
M = {{1, 3, 3},
     {2, 1, 4},
     {0, 6, 4}};
Output: 12
Explaination: 
The path is {(1,0) -> (2,1) -> (2,2)}.


Example 2:

Input: n = 4, m = 4
M = {{1, 3, 1, 5},
     {2, 2, 4, 1},
     {5, 0, 2, 3},
     {0, 6, 1, 2}};
Output: 16
Explaination: 
The path is {(2,0) -> (3,1) -> (2,2) 
-> (2,3)} or {(2,0) -> (1,1) -> (1,2) 
-> (0,3)}.


Your Task:
You do not need to read input or print anything. Your task is to complete the function maxGold() which takes the values n, m and the mine M as input parameters and returns the maximum amount of gold that can be collected.


Expected Time Complexity: O(n*m)
Expected Auxiliary Space: O(n*m)


Constraints:
1 ≤ n, m ≤ 50
1 ≤ M[i][j] ≤ 100



solution:

// User function Template for C++


class Solution{

public:

    int maxGold(int n, int m, vector<vector<int>> M)

    {

        vector<vector<int>>r(n , vector<int>(m , -1));

        int maxi = INT_MIN;

        if(m == 1)

        {   

            for(int i = 0 ; i < n ; i++)

            {

                if(maxi < M[i][m-1])

                 maxi = M[i][m-1];

            }

            return maxi;

        }

        if( n == 1)

        {   

            int sum = 0;

            for(int i = 0 ; i < m ; i++)

            {

                sum = sum + M[n-1][i];

            }

            return sum;

        }

        

        for(int j = 0 ; j < m ; j++)

        {

            for(int i = 0; i < n ; i++)

            {

                if(j == 0)

                {

                    r[i][j] = M[i][j];

                }

                else

                if(i == 0)

                {

                    r[i][j] = M[i][j] + max(r[i][j-1] , r[i+1][j-1]);

                }

                else

                if(i == n-1)

                {

                    r[i][j] = M[i][j] + max(r[i][j-1] , r[i-1][j-1]);

                }

                else

                if(i < n-1 && i > 0 && j > 0)

                r[i][j] = M[i][j] + max ({r[i-1][j-1] , r[i][j-1] , r[i+1][j-1]});

                if(maxi < r[i][j])

                 {

                     maxi = r[i][j];

                 }

            }

        }

        return maxi;

    }

};

Labels:

Comments

Post a Comment

Popular posts from this blog

leetcode 48 solution

  48 .  Rotate Image You are given an  n x n  2D  matrix  representing an image, rotate the image by  90  degrees (clockwise). You have to rotate the image  in-place , which means you have to modify the input 2D matrix directly.  DO NOT  allocate another 2D matrix and do the rotation.   Example 1: Input: matrix = [[1,2,3],[4,5,6],[7,8,9]] Output: [[7,4,1],[8,5,2],[9,6,3]] Example 2: Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]] Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]   Constraints: n == matrix.length == matrix[i].length 1 <= n <= 20 -1000 <= matrix[i][j] <= 1000 solution: class Solution { public:     void swap(int& a , int &b)     {         int c ;         c = a;         a = b;         b = c;     }     void transpose (vector<vector<int>...
Post a Comment
Read more

2485. Find the Pivot Integer | Binary search

  Given a positive integer   n , find the   pivot integer   x   such that: The sum of all elements between  1  and  x  inclusively equals the sum of all elements between  x  and  n  inclusively. Return  the pivot integer  x . If no such integer exists, return  -1 . It is guaranteed that there will be at most one pivot index for the given input.   Example 1: Input: n = 8 Output: 6 Explanation: 6 is the pivot integer since: 1 + 2 + 3 + 4 + 5 + 6 = 6 + 7 + 8 = 21. Example 2: Input: n = 1 Output: 1 Explanation: 1 is the pivot integer since: 1 = 1. Example 3: Input: n = 4 Output: -1 Explanation: It can be proved that no such integer exist.   Constraints: 1 <= n <= 1000 Solution : class Solution { publ ic:     int pivotInteger( int n ) {         int sum = (( n )*( n + 1 ))/ 2 ;         int i = 1 ;         int j =...
Post a Comment
Read more

Regular Expression Matching Leetcode Solution

Regular Expression Matching Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where: '.' Matches any single character.​​​​ '*' Matches zero or more of the preceding element. The matching should cover the entire input string (not partial). Example 1: Input: s = "aa", p = "a"  Output: false  Explanation: "a" does not match the entire string "aa". Example 2: Input: s = "aa", p = "a*"  Output: true  Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa". Example 3: Input: s = "ab", p = ".*"  Output: true  Explanation: ".*" means "zero or more (*) of any character (.)". Constraints: 1 <= s.length <= 20 1 <= p.length <= 20 s contains only lowercase English letters. p contains only lowercase Englis...
Post a Comment
Read more