What is the thinking process behind this DP solution?
Apart from the algorithm which has been explained in the video, I want to know the logical thinking process which explains why this particular solution was used for this problem and why not some other solution.
For eg: you can tell about the very naive solution which comes to mind and then how you think about optimizing it which might lead to this DP solution.
for a problem first we come up with a naive approach
and because of its high time complexity it will give TLE
so we have to optimize it
if the naive solution has two features then we can use dynamic programming for optimization
1) Optimal Substructure:
a problem is said to have optimal substructure if an optimal solution can be constructed from optimal solutions of its subproblems.
2) Overlapping Subproblems
it means some part of problem is calculated multiple times
if these 2 property holds then you can try its dp solution
So, can you tell me what would be the algo for its naive solution?