Блог

Я пытаюсь решить проблему Золотого прииска в GFG, используя подход динамического программирования, основанный на запоминании. Вот код, который я написал.

 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) времени.

Может ли кто-нибудь помочь мне с тем, как обойти эту проблему оптимального определения того, с какой ячейки начинать, чтобы подход, основанный на запоминании, работал в условиях ограничений по времени?

Используйте ссылку call by const для контейнера STL. Вы выполнили тысячи копий полного ввода, доступного только для чтения.

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

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

вот мое решение:

 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;
    }
};