Optimal binary search tree problem in DP

#1

this is standarad problem in geek for geeks.i am unable to think dynamic approach.please help me to solve this.

#2

@SOHAN
better to think it recursively.
so lets suppose you are current element i, where i is from 0 to n-1.
so for that current element you have to choices

  1. Either to include that element in the subset which you are going to make. So if you select it then call the recursion for remaining cases. the remaining cases are after taking this element you can still choose to take that.
    the recursive call will look like recursion(cap - val[i], i)
  2. The case is to not select this element and move to next.
    so recursive call is recursion(cap, i+1)

you can also have a look at this recursive code of mine for better understanding. btw this question is just same as 0-1 Knapsack, the extra condition is that we can take an element more than once.

Please mark the doubt as resolved if you find it helpful

#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.