Untitled

mail@pastecode.io avatar
unknown
plain_text
23 days ago
1.3 kB
1
Indexable
Never
class Solution {
public:
    int cherryPickup(vector<vector<int>>& grid) {
        int r=grid.size(), c=grid[0].size();
        vector<vector<vector<int>>>dp(r,vector<vector<int>>(c,vector<int>(c,INT_MIN))); //max cherries robo can take on ith row and j,kth col
        dp[0][0][c-1]=grid[0][0] + (c > 1 ? grid[0][c-1] : 0);
        for(int i=1;i<r;i++){
            for(int j=0;j<c;j++){
                for(int k=j+1;k<c;k++){
                    int prev=-1;
                    for(int p=max(0,j-1); p<=min(c-1,j+1); p++){
                        for(int q=max(0,k-1);q<=min(c-1,k+1);q++){
                            prev=max(prev,dp[i-1][p][q]);
                        }
                    }
                    if(prev!=-1){
                        dp[i][j][k]=prev+grid[i][j];
                        if(j!=k) dp[i][j][k]+=grid[i][k];
                    }
                }
            }
        }
        int res=INT_MIN;
        for(int i=0;i<c;i++){
            for(int j=0;j<c;j++){
                res=max(res,dp[r-1][i][j]);
            }
        }
        return res;
    }
};


                    //dp[i][j][k]=grid[i][j] + max(dp[i-1][j-1][k],max(dp[i-1][j][k],dp[i-1][j+1][k]))+ grid[i][k]+ max(dp[i-1][j][k-1],max(dp[i-1][j][k+1],dp[i-1][j][k]));
Leave a Comment