Simple O(n) Top Down DP approach


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