Best DP solution O(n*m) CPP


#1
int Solution::solve(vector<vector<int> > &A) {

int n =A.size(),m=A[0].size();
int dp[n][m];

memset(dp,0,sizeof(dp));

for(int i=0;i<n;i++)
{
    for(int j=0;j<m;j++)
    {
        if(i==0)
        dp[i][j]=A[i][j];
        
        else if(j==0)
        {
            dp[i][j]=A[i][j]+min(dp[i-1][j+1],dp[i-1][j+2]);
        }
        else if(j==m-1)
        {
            dp[i][j]=A[i][j]+min(dp[i-1][j-1],dp[i-1][j-2]);
        }
        else
        {
            dp[i][j]=min(dp[i-1][j-1],dp[i-1][j+1])+A[i][j];
        }
    }
}
int ans=INT_MAX;

for(int j=0;j<m;j++)
ans=min(ans,dp[n-1][j]);

return ans;

}


#2

Update your definition of “best”!!!

int Solution::solve(vector<vector<int> > &a) {
        int n = a.size();
        
        for(int i=1;i<n;i++){
            for(int j=0;j<3;j++)
            a[i][j] += min(a[i-1][(j+1)%3], a[i-1][(j+2)%3]);
        }
        return min(a[n-1][0], min(a[n-1][1], a[n-1][2]));
    }