Suggest the right approach

#1

how to use bottom up dp in this

#2

Hi @irohan
Best approach to solve this problem using two pointer approach in O(n) time by maintaining a sub-array which contains maximum k 0’s.
If you want to do it with Dynamic programming(not recommended) , O(n*k), work in this fashion

for(i =0 to k) // flips available
{
for(j=0 to n) //traversing array
{
if(1) then dp[i][j]=1+dp[i][j-1]
if(0) then dp[i][j]=max(1+dp[i-1][j-1] , dp[i][j-1])
}
}

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#4

if(0) then it will come max ( 1+ dp[i-1][j-1] , dp[i-1][ j ] )
dp[i][j-1] will not work

#5

If k = 0 , then dp[i[[j[ = ar[i] [j] since no flipping available. So whatever is the value becomes the answer for corresponding dp block