动态规划
暴力算法几乎可以解决一切问题。回溯算法的特点是，通过暴力尝试不同分支，最终选择结果最优的线路。
而动态规划也有分支概念，但不用把每条分支尝试到终点，而是在走到分叉路口时，可以直接根据前面各分支的表现，直接推导出下一步的最优解！然而无论是直接推导，还是前面各分支判断，都是有条件的。动态规划可解问题需同时满足以下三个特点：
存在最优子结构。 存在重复子问题。 无后效性。
存在最优子结构
即子问题的最优解可以推导出全局最优解。 dp[i] = dp[i-1]+dp[i-2] 全局 子问题 推导 子问题
存在重复子问题
即同一个子问题在不同场景下存在重复计算。
比如寻路算法中，同样两条路线的计算中，有一段路线是公共的，是计算的必经之路，那么只算一次就好了，当计算下一条路时，遇到这个子路，直接拿第一次计算的缓存即可。典型例子是斐波那契数列，对于 f(3) 与 f(4)，都要计算 f(1) 与 f(2)，因为 f(3) = f(2) + f(1)，而 f(4) = f(3) + f(2) = f(2) + f(1) + f(2)。
这个是动态规划与暴力解法的关键区别，动态规划之所以性能高，是因为 不会对重复子问题进行重复计算，算法上一般通过缓存计算结果或者自底向上迭代的方式解决，但核心是这个场景要存在重复子问题。
当你觉得暴力解法可能很傻，存在大量重复计算时，就要想想是哪里存在 重复子问题，是否可以用动态规划解决了。
无后效性
即前面的选择不会影响后面的游戏规则。
寻路算法中，不会因为前面走了 B 路线而对后面路线产生影响。斐波那契数列因为第 N 项与前面的项是确定关联，没有选择一说，所以也不存在后效性问题。
有同学可能觉得这样局限是不是很大？其实不然，无后效性的问题仍然很多，比如背包放哪件物品、当前走哪条路线、用了哪些零钱，都不会影响整个背包大小、整张地图的地形、以及你最重要付款的金额
解法套路 - 状态转移方程
解决动态规划问题的核心就是写出状态转移方程，所谓状态转移，即通过某些之前步骤推导出未来步骤。
状态转移方程一般写为 dp(i) = 一系列 dp(j) 的计算，其中 j < i
爬楼梯
先考虑普通缓存减少计算开销
再考虑滚动缓存减少空间开销
如果遇到用到之前所有缓存的状态转移方程，就无法使用滚动缓存方案了。然而还有更高级的多维缓存
最长有些括号
如果 s[i] 是 (，那么不可能组成有效括号，因为最右边一定不闭合，
所以考虑 s[i] 为 ) 的场景。
如果 s[i-1] 为 (，那么构成了 ...() 之势，最后两个自成合法闭合，所以只要看前面的即可，即 dp(i-2)，所以这种场景的状态转移方程为
dp(i) = dp(i-2) + 2
如果 s[i-1] 是 ) 呢？构成了 ...)) 的状态，那么只有 i-1 是合法闭合的，且这个合法闭合段之前必须是 ( 与第 i 项形成闭合，才构成此时最长有效括号长度，所以这种场景的状态转移方程为：
dp(i) = dp(i-1) + dp(i - dp(i-1) - 2) + 2，你可以结合下面的图来理解：
( ) ( ()() )
_____________ ____ s[i]
dp[i-dp(i-1)-2] dp[i-1]
栅栏涂色
有 k 种颜色的涂料和一个包含 n 个栅栏柱的栅栏，每个栅栏柱可以用其中一种颜色进行上色。
你需要给所有栅栏柱上色，并且保证其中相邻的栅栏柱 最多连续两个 颜色相同。然后，返回所有有效涂色的方案数。
这道题 k 和 n 都非常巨大，常规暴力解法甚至普通 DP 都会超时。选择 i 的含义也很重要，这里 i 到底代表用几种颜色还是几个栅栏呢？选择栅栏会好做一些，因为栅栏是上色的主体。这样 dp(i) 就表示上色前 i 个栅栏的所有涂色方案。
首先看下递归终止条件。由于最多连续两个颜色相同，因此
- dp(0) 是 k（一个栅栏）
- dp(1) 是 k*k，因为每个栅栏随便刷颜色，自由组合。
- dp(2) 有三个栅栏，非法情况是三个栅栏全同色，所以用所有可能减掉非法即可，非法场景只有 k 中，所以结果是 k*k*k - k。
那么考虑一般情况，对于 dp(i) 有几种涂色方案呢？直接思考情况太多，我们把情况一分为二，考虑 i 与 i-1 颜色相同与不同两种情况考虑。
-
如果 i 与 i-1 颜色相同，那么为了合法，i-1 肯定不能与 i-2 颜色相同了，否则就三个同色，这样的话，不管 i-2 是什么颜色，i-1 与 i 都只能少取一种颜色，少取的颜色就是 i-2 的颜色，因此 [i-1,i] 这个区间有 k-1 中取色方案，前面有 dp(i-2) 种取色方案，相乘就是最终方案数：dp(i-2) * (k-1)。
-
如果 i 与 i-1 颜色不同，那么第 i 项只有 k-1 种取法，一样也是动态的，因为永远不能和 i-1 颜色相同。最后乘上 dp(i-1) 的取色方案，就是总方案数：dp(i-1) * (k-1)。
所以最后总方案数就是两者之和，即 dp(i) = dp(i-2) (k-1) + dp(i-1) (k-1)。
这道题的不同之处在于，变化太多，任何一个栅栏取的颜色都会影响后面栅栏要取的颜色，乍一看觉得是个有后效性的题目，无法用动态规划解决。但实际上，虽然有后效性，但如果进行合理的拆解，后面栅栏的总可能性 k-1 是不变的，所以考虑总可能性数量，是无后效性的，因此站在方案总数上进行抽象思考，才可能破解此题。
编辑距离
假设最后一个字符相同，即 word1[i] === word2[j] 时，由于最后一个字符不用改就相同了，所以操作次数就等价于考虑到前一个字符，即 dp(i,j) = dp(i-1,j-1)
假设最后一个字符不同，那么 最后一步 有三种模式可以得到：
假设是替换，即 dp(i,j) = dp(i-1,j-1) + 1，因为替换最后一个字符只要一步，并且和前面字符没什么关系，所以前面的最小操作次数直接加过来。 假设是插入，即 word1 插入一个字符变成 word2，那么只要变换到这一步再 +1 插入操作就行了，变换到这一步由于插入一个就行了，因此 word1 比 word2 少一个单词，其它都一样，要变换到这一步，就要进行 dp(i,j-1) 的变换，因此 dp(i,j) = dp(i,j-1) + 1。。 假设是删除，即 word1 删除一个字符变成 word2，同理，要进行 dp(i-1,j) 的变化后多一步删除，因此 dp(i,j) = dp(i-1,j) + 1。 由于题目取操作最少次数，所以这三种情况取最小即可，即 dp(i,j) = min(dp(i-1,j-1), dp(i,j-1), dp(i-1,j)) + 1。