1 count dynamic programming

#1

i am trying to solve it as sliding window, i am unable to figure how is this a DP problem…since the window issliding and the 2 pointers left and right just moving forward,so there is no overlapping also…?

#2

Hello @Vibhuti0206

What Dynamic Programming is storing some information (for later use) so that you don’t need to compute that information again.

Let us say we have the array
0 0 1 1 0 1 0 1 1 1 0 0 and we can change at max k 0’s to 1’s

Now how can we solve this problem is, for every 0 go and search to its left (k - 1) zero’s, change all of them to 1 and go left while we get 1 and Now update maxLength of sub-array
Time complexity is O(n^2).

What the left pointer in the optimized way (O(n)) is doing is, it is helping us to store information relating to the searching of (k - 1) zero’s and hence it is a DP problem.

I hope that I have cleared your doubt.
Let me know if you still need any help.