动态规划

Dynamic Programming
DP定义∶
动态规划是分治思想的延伸，通俗一点来说就是大事化小，小事化无的艺术。
在将大问题化解为小问题的分治过程中，保存对这些小问题已经处理好的结果，并供后面处理更大规模的问题时直接使用这些结果。
动态规划具备了以下三个特点：
1.把原来的问题分解成了几个相似的子问题。
2.所有的子问题都只需要解决一次。
3.储存子问题的解。
动态规划的本质，是对问题状态的定义和状态转移方程的定义(状态以及状态之间的递推关系)
动态规划问题一般从以下四个角度考虑:
1.状态定义
2.状态间的转移方程定义
3.状态的初始化
4.返回结果
状态定义的要求:定义的状态一定要形成递推关系。
适用场景:最大值/最小值,可不可行，是不是，方案个数





**