1 count DP Problem

#1

This problem can be solved by using two pointers. How to solve it by using Dynamic Programming?

#2

Hello @gsinha783,

Why do you think that this problem can be solved using DP?
Can you answer this?

A problem can be solved using DP if it satisfies two properties:

  1. Overlapping Sub-structures: It refers to the problem when solutions of same subproblems are needed again and again. In dynamic programming, computed solutions to subproblems are stored in a table so that these don’t have to be recomputed. So Dynamic Programming is not useful when there are no common (overlapping) subproblems because there is no point storing the solutions if they are not needed again.
  2. Optimal Sub problems: A given problems has Optimal Substructure Property if optimal solution of the given problem can be obtained by using optimal solutions of its subproblems.

So, can you connect this problem with DP?

Hope, this would help.
Give a like, if you are satisfied.

#3

Because this problem was given in the challanges section of Dynamic Programming.

#4

LOL:joy:
I mean to ask, can you relate it with DP?

#5

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.