What is dynamic programming?
Dynamic programming is the way of solving a problem by applying the same solution repeatedly on the partial problem through recursion.
It mainly used in the optimization problem that could satisfy that optimize its sub-problem could contribute to optimizing the problem as a whole. We call that problem has a substructure.
For example, if your life is an optimization problem, what is the criteria that you want to optimize? such as happiness, right? We call that happiness is the value function. If your happiness is high, it is good. You want to optimize the happiness high for the whole of your life or just high at the end of your life? Obviously, you want to break your lifetime into smaller chunks and optimize the happiness at that moment to make sure it high and it will help the next chunk of your lifetime also good too.
So we could call maximize your happiness in life is an optimal substructure problem.
Besides the value function, that is the target for you to go to optimize, you have the input values that affect your happiness such as money, work, relationship. We call that the state. And the current state could change the next state in the future through some function or policy that we call control function
Another example of dynamic programming is the Fibonacci sequence. For you to calculate the nth Fibonacci number, you have to calculate the nth - 1 and nth - 2 in advance and keep so on until you get to the 1st and 2nd Fibonacci numbers.
Conclusion
Dynamic programming helps us to specify the solution for the problem in a very intuitive way. When we go for the searching problem or optimization problem, try to break it down into smaller problems and apply dynamic programming could create a very elegant solution