GFG 上金矿问题的记忆化方法

Question

我正在尝试使用基于记忆的动态规划方法解决 GFG 上的 Gold Mine problem。这是我写的代码。

int dp[50][50];


int traverse(int x,int y,int n,int m, vector<vector<int>> M){
    
    if((x<n and x>=0) and (y<m and y>=0))
        {
        
            if(dp[x][y]!=-1)
                return dp[x][y];
            else{
                
            
                int right=M[x][y]+traverse(x,y+1,n,m,M);
                int right_up=M[x][y]+traverse(x-1,y+1,n,m,M);
                int right_down=M[x][y]+traverse(x+1,y+1,n,m,M);
                return dp[x][y]=max(max(right,right_up),right_down);}
            
        }
    return 0;
    
    
    
}

int maxGold(int n, int m, vector<vector<int>> M)
{
    
    
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            dp[i][j]=-1;
        }
    }
    int ans=0;
    for(int i=0;i<n;i++){
        ans=max(ans,traverse(i,0,n,m,M));
    }
    return ans;

 }

问题说我们可以从第一列的任何单元格开始。由于未指定特定的单元格，我尝试以第一列的每个单元格为起点找出所有可能答案的最大值。但这给出了一个 TLE，这是预期的，因为上面的代码将花费 o(n^2*m) 时间。

任何人都可以帮助我解决如何最佳地确定从哪个单元格开始的问题，以便基于记忆的方法在提供的时间限制下工作吗？

Answer 1

对 STL 容器使用常量引用调用。您执行了数千份完整的只读输入。

int dp[55][55];
int traverse(int x,int y,int n,int m, const vector<vector<int>>&M){
    . . .
}

int maxGold(int n, int m, const vector<vector<int>>&M)`
{
    ...
}

Answer 2

这是我的解决方案：

class Solution{
public:
    int maxGold(int n, int m, vector<vector<int>> M)
    {
        vector<vector<int>> f(n + 10, vector<int>(m + 10, 0));
        
        for(int i = 0; i < n; i++){
            f[i][0] = M[i][0];
        }
        
        for(int j = 1; j < m; j++){
            for(int i = 0; i < n; i++){
                if(i == 0){
                    f[i][j] = max(f[i][j-1], f[i+1][j-1]) + M[i][j];
                }else if(i == n-1){
                    f[i][j] = max(f[i][j-1], f[i-1][j-1]) + M[i][j];
                }else{
                    f[i][j] = max({f[i][j-1], f[i-1][j-1], f[i+1][j-1]}) + M[i][j];
                }
            }
        }
        
        int res = 0;
        for(int i = 0; i < n; i++){
            res = max(res, f[i][m-1]);
        }
        return res;
    }
};

GFG 上金矿问题的记忆化方法

Memoization Approach for Gold Mine Problem on GFG

c++

algorithm

dynamic-programming