Dynamic Programming Solution - Not Working Why?


#1

int Solution::solve(vector &A, int B) {
int n=A.size();
int dp[n+1][B+1];
for(int i=0; i<=B; i++) dp[0][i]=0;
if (n==0) return 0;
dp[0][0] = 0;
dp[1][0] = A[0];
for(int i=1; i<=n; i++) {
if (A[i]==1 and A[i-1]!=0) dp[i][0]=1+dp[i-1][0];
else if (A[i-1]==0 and A[i]==1) dp[i][0] = max(dp[i-1][0],1);
else dp[i][0]=dp[i-1][0];
}
for(int i=1; i<=n; i++){
for(int j=1; j<=B; j++){
if (A[i]==1) dp[i][j]=1+dp[i-1][j];
else{
dp[i][j] = max(1+dp[i-1][j-1], dp[i-1][j]);
}
}
}
return dp[n][B];
}