个人对DP的本质理解：一种解决问题的思路。当问题无法显示的用公式表达出来或者表达出来非常复杂，就可以想到用动态规划。
用数据公式可以表示，最简单的菲波拉契计算如下所示：
f(n) = f(n-1) + f(n-2)可以形象理解成如何将N的求解与N-1、N-2等关联起来，然后用递归的方式计算出答案。
比如说爬阶梯的问题：
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）这里要采用逆向思维解决问题，因为正向的解决是显式解决，需要计算出一个公式，这里实现不了。
第n个台阶可以是n-1跳一级台阶上来的，也可以是n-2跳二个台阶上来的。所以
f(n) = f(n-1) + f(n-2)
f(1) = 1
f(2) = 2class Solution:def climb_stairs(self, n):""":type n: int:rtype: int"""dp = [1] * n #状态的定义for i in range(2,n+1):dp[i] = dp[i-1]+dp[i-2] #状态转移方程return dp[n]
三色排列问题的解决方案：
有排成一行的ｎ个方格，用红(Red)、粉(Pink)、绿(Green)三色涂每个格子，每格涂一色，要求任何相邻的方格不能同色，且首尾两格也不同色．求全部的满足要求的涂法.假设有5个格子。ABCDE
错误的方法、
A可以填写3种颜色，B不与A相同可以填写2种颜色，C不与B相同可以填写2种颜色，
D不与C相同可以填写2种颜色，E不与A和D相同只可以填写1种颜色。
所以3*2*2*2*2*1,抽象的公式 $\3*2^{n-2}$；但这结果是错误的，为什么呢？最后一个格子的考虑不完备，E不与A和D相同，潜意识里认为AD也不同。但还存在A与D相同的情况。AD相同会有两种。所以AD不同时，D有两种，E只有一种选择，所以3*2*2*2*1，当AD相同时，D没有选择，E有两种选择，3*2*2*1*2就将公式抽象成3*2^{n-3}*3。这结果仍然是错误的，为什么呢？因为D本质上只有两个选择，而上述方案给了D三个选择，多出了一个，为什么呢，因为D必须要与C不同，所以前面的系数不能是3*2*2了。（这里太烧脑了）DP方法：
DP的求解过程本质就是如何去掉n。回归到这个问题，就是如何去掉E；这里可以分成AD同色和不同色的情况，AD不同色，E只有一种选择，此时去掉E，前n-1个格子的颜色完全满足条件，所以就等同于求解f(n-1)；如果AD同色，E有两种选择，但仅仅去掉E是不行的，因为AD同色不满足条件。那么此时去掉D，效果怎么样呢，因为CD不同色，所以此时AC不同色，前n-2个格子完全满足条件，所以满足f(n-2)的条件。所以最终的公式：f(n) = f(n-1) + 2*f(n-2)。最后求解两个初始值，f(1) = 3 , f(2) = 6, f(3) = 6.这里求解一般容易漏掉3这个特殊值。因为这里的格子只有三类，起始位置，中间位置，结束位置。如何才能快速定位到使用DP规划求解问题呢，提高效率？