# 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) --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://aaronice.gitbook.io/lintcode/dynamic_programming.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.