> For the complete documentation index, see [llms.txt](https://aaronice.gitbook.io/lintcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://aaronice.gitbook.io/lintcode/dynamic_programming.md). # Dynamic Programming ## 动态规划的4点要素 1 . **状态 State** * 灵感,创造力,存储小规模问题的结果 * 最优解/Maximum/Minimum * Yes/No * Count 2 . **方程 Function** * 状态之间的联系,怎么通过小的状态,来求得大的状态 3 . **初始化 Initialization** * 最极限的小状态是什么, 起点 4 . **答案 Answer** * 最大的那个状态是什么,终点 ## 动态规划中的优化 ### 滚动数组优化 ``` f[i] = max(f[i-1], f[i-2] + A[i]); ``` 转换为 ``` f[i%2] = max(f[(i-1)%2]和 f[(i-2)%2]) ``` #### 一维滚动数组优化 这类题目特点 `f[i] = max(f[i-1], f[i-2] + A[i])`; 由 `f[i-1],f[i-2]` 来决定状态 可以转化为 `f[i%2] = max(f[(i-1)%2]`和 `f[(i-2)%2])` 由 `f[(i-1)%2]` 和 `f[(i-2)%2]` 来决定状态 观察我们需要保留的状态来确定模数 #### 二维动态规划空间优化 这类题目特点 `f[i][j]` = 由`f[i-1]`行 来决定状态, 第`i`行跟 `i-1` 行之前毫无关系 所以状态转变为 `f[i%2][j]` = 由`f[(i-1)%2]`行来决定状态 ## 记忆化搜索 * 本质上: 动态规划 * 动态规划就是解决了**重复计算**的搜索 * 动态规划的实现方式: * 循环(从小到大递推) * 记忆化搜索(从大到小搜索) * 画搜索树 * 万金油 ### 什么时候用记忆化搜索? * 状态转移特别麻烦,不是顺序性。 * Longest Increasing continuous Subsequence 2D * 遍历x,y 上下左右四个格子 `dp[x][y] = dp[nx][ny]` * Coins in a Line III * `dp[i][j] = sum[i][j] - min(dp[i+1][j], dp[i][j-1])`; * 初始化状态不是很容易找到 * Stone Game * 初始化`dp[i][i] = 0` * Longest Increasing continuous Subsequence 2D * 初始化极小值 * 从大到小 ## 博弈类DP 博弈有先后手 * State * 定义一个人的状态 * Function * 考虑两个人的状态做状态更新 * Initialize * Answer 先思考最小状态，然后思考大的状态 -> 往小的状态地推，那么非常适合记忆化搜索 ## 区间类DP 区间类DP特点: 1. 求一段区间的解max/min/count 2. 转移方程通过区间更新 3. 从大到小的更新 区间类DP的做法，是用memorized search，把大区间拆分为小区间来解。而`dp[i][j]` 则直观的表示为区别 `i` 到 `j` 的最优解。 Example: * [Coins in a Line III](/lintcode/dynamic_programming/coins_in_a_line_iii.md) * [Stone Game](/lintcode/dynamic_programming/stone_game.md) * [Burst Balloons](/lintcode/dynamic_programming/burst-balloons.md) * Scramble String 这种题目共性就是区间最后求\[0,n-1] 这样一个区间。\ 逆向思维分析 从大到小就能迎刃而解。 逆向 =>> 分治类似 ## 划分类DP Reference: “划分类” DP，是指给定原数组之后，将其划分为 k 个子数组，使其 sum / product 最大 / 最小的 DP 类问题。 这类问题的 optimal substructure 是，对于给定区间的globalMax，其最优解一定由所属区间内的 localMax 区间组成，可能不连续。 以“必须以当前结尾” 来保证 local 子问题之间的连续性；用 global 来记录最优解之间可能的不连续性。 划分类DP 与 区间类DP 主要区别在于，我们只取其中 k 段，而中间部分可以留空；而区间类 DP 子问题之间是连贯而不留空的。区间类 DP 是记忆化的 divide & conquer, 划分类 DP 则是不连续 subarray 的组合，不同于区间类 DP 每一个区间都要考虑与计算，划分类DP 很多元素和子区间是可以忽略的，有贪心法的思想在里面，因此也依赖于正确的 local / global 结构来保证算法的正确性。 ## 背包类DP 背包类DP 特点: 1. 用值作为DP维度 2. DP过程就是填写矩阵 3. 可以滚动数组优化 ## 其他 ### 何时可能使用DP * 求最大最小值 max/min * 求能否达到 yes/no * 求数量 count(\*) ### 编程小技巧 * 多开一位，把0位空出来 ## 参考资料 * [Hawstein: 动态规划：从新手到专家](http://www.hawstein.com/posts/dp-novice-to-advanced.html) * [什么是动态规划？动态规划的意义是什么?](https://www.zhihu.com/question/23995189)