The process of reading a problem and applying dynamic programming to it has always seemed flimsy to me. Even after getting accepted, I do not feel like I fully understand the state and transitions that I’ve come up with.
Is there a way to prove that the recurrence relation behind the dp actually reflects the structure of a problem?
Are there any books which explain in depth how to come up with the recurrence relations that appear in dynamic programming problems?
For optimizing DP, the key property that is required for DP to work is optimal substructure. This means that a solution can be constructed from an optimal solution of its subproblems. If you can prove optimal substructure with the states you're using and prove the transitions then you can prove the DP.
Combinatorial DP or trivial DP such as Fibonacci numbers are easier to prove.
Recursive spec :)
Many DP can be modeled as, I'm currently at state
v, and I could perform actions to go to one ofa,b, orc. Then, inductively/recursively, solve those.