动态规划总结篇

dynamic programming, DP

什么是动态规划？

一句话解释：大事化小，小事化了
简单的解释：想办法将一个复杂的大问题拆成几个子问题，分别求解这些子问题，从而求出大问题的解。

什么样的题适合用DP求解？

具有以下两点特征的问题可以用DP求解：

1. 重叠子问题（Overlapping Subproblems）：有些子问题会被重复计算多次。
2. 最优子结构（Optimal Substructure）：问题的最优解可以从某个子问题的最优解中获得。

如何设计DP：

DP的核心是状态和状态转移方程：
状态：描述该问题的子问题的解，即根据子问题来定义状态。
状态转移方程：状态和状态之间的关系式。大部分情况下，某个状态只与它前面出现的状态有关，而独立于后面的状态（比如 斐波那契数列 f(n)=f(n-1)+f(n-2)）。

动态规划的解题思路：

1. 将原问题分解为子问题；
2. 确定状态：状态不是随便定义的，一般定义完就要找到状态转移方程；
3. 确定一些初始状态（边界状态）的值；
4. 确定状态转移方程。

如果问题看起来是个动态规划问题，但是无法定义出状态，那么可以试着将问题规约到一个已知的 DP 问题。

两种设计思路：

1. 默记法（从上到下）/ Memoization (Top Down)：设置一个数组，当需要子问题的解时，先去这个数组中查找。如果此问题之前已经求过解，那么就直接返回该值，如果此问题之前并未求过解，那么就计算该值并把结果放入数组中，以备后用。
2. 表格法（从下到上）/ Tabulation (Bottom Up)：用迭代法建立一个表格，从该表格中返回所需的值。
   p.s.有时候会将默记法作为单独的一种方法。比如在 leetcode300的题解 中，会分为带记忆的递归(Recursion with Memoization)和动态规划(Dynamic Programming)方法，此时的DP方法特指表格法。

例题

从例题中学习才是最直接、有效的.

入门题

leetcode70爬楼梯:本题适合入门，题解分别阐释了两种设计思路(自上而下、自下而上)的实现。

普通题

leetcode300最长上升子序列

进阶题

leetcode44通配符匹配:本题属于二维动态规划，从这道题中可以直观的体会为什么自下而上的方法又叫表格法。
leetcode712两个字符串的最小ASCII删除和:本题属于二维动态规划，从这道题中可以直观的体会为什么自下而上的方法又叫表格法。