Sherlock and Cost Discussions | Algorithms | HackerRank
  • + 0 comments

    Bottom up DP

    int cost(vector<int> B) {
    vector<vector<int>>dp(B.size(),vector<int>(2,0));
    int n=dp.size()-1;
    for(int i=1;i<B.size();i++){
        dp[i][0]=max(dp[i-1][0],dp[i-1][1]+abs(B[i-1]-1));
        dp[i][1]=max(dp[i-1][0]+abs(B[i]-1),dp[i-1][1]+abs(B[i]-B[i-1]));
    }
    return max(dp[n][0],dp[n][1]);
    
    }