Not able to convert the recursive code to DP


#1
  1. int n;
  2. vector<int> dp;
  3. vector<vector<int>> A;
  4. int fin_start(int i, int sum)
  5. {
  6. if(i>=n)
  7. return sum;
  • int x = fin_start(i+2,sum+max(A[0][i], A[1][i]));
  1. int y = fin_start(i+1,sum);
  • dp[i] = max(x,y);
  1. return max(x,y);
  2. }
  • int Solution::adjacent(vector<vector<int> > &a) {
  1. n = a[0].size();
  2. dp.resize(n);
  3. A=a;
  4. return fin_start(0,0);
  • }

#2

Here is iterative approach :-1:
int Solution::adjacent(vector<vector > &A) {
int m=A[0].size();
int m0=max(A[0][0],A[1][0]);
if(m==1)
return m0;
int m1=max(A[0][1],A[1][1]);
for(int j=2; j<m;j++) {
A[0][j]+=m0;
A[1][j]+=m0;
m0=max(m1,m0);
int k=max(A[0][j],A[1][j]);
m1=max(k,m1);
}

return max(m0,m1);

}