1. 定义

动态规划（Dynamic Programming, DP）与分治策略（Divide and Conquer, D&C）比较类似都是将一个问题划分成许多子问题，主要用于求解优化问题。动态规划是用空间换时间，记录过程信息的典型算法。

包括：

1. 状态定义
2. 状态方程
3. 边界问题
4. 结果返回

1.1 状态定义

也叫问题定义，常见问题的定义范围有：

1. 一维的数组dp[i]
2. 二维的数组dp[i][j]
3. 三维的数据dp[i][j]

1.2 状态方程

也叫状态转移方程，即当下步骤和上一步骤的状态是如何变化的，这样当当下步骤信息记录后，下一步就可以直接从数组中查询结果了。
eg: dp[i] = dp[i-1] + 1

1.3 边界问题

边界是指问题在定义的规模内的边界上如何处理，常见的边界就是：

1. 第一步可以直接看出默认值，eg: dp[0] = 0
2. 最后一步可以直接看出默认值，eg: dp[M]= -1

1.4 结果返回

问题的所有步骤都已经记录在了dp数组中，根据题目要求从数组中找到并加工结果即可

2. 演化路径

2.1 暴力递归

递归过程需要：

1. 找到当前步骤和之前(or 之后)步骤的关系，对应的就是动态转移方程
2. 设置好递归终止条件bad case，对应的就是动态规划的边界

由上可以看出，递归 + 过程数据存储 = 动态规划

所以，暴力递归和动态规划的关系：

1. 某一个暴力递归，有解的重复调用，就可以把这个暴力递归优化成动态规划
2. 任何动态规划问题，都一定对应着某一个有解的重复调用的暴力递归
3. 但不是所有的暴力递归对对应着一个动态规划

2.2 记忆化搜索

在递归的过程中加入过程数据存储就可以改造称为记忆化搜索，

1. 因为递归的过程可能会调用到某些已经求过的重复子问题
2. 我们将这些子问题的解保持在特定的数据结构中
3. 递归的过程用到的时候，从数据结构中查询过来直接使用

即： 递归 + 过程数据存储 = 动态规划

2.3 严格表结构DP

递归加上数组后重新看下动态规划的步骤：

1. 问题的规模到底是多太，是取决于递归过程中的可变参数来决定的
2. 最后位置：当初暴力递归函数里面的可变参数的传进去的值 (从主函数里面的调用的时候)
3. bad case：递归函数里面的 base case 标出不用算直接可以获取答案的下标的那些元素
4. 依赖关系：递归函数的主体部分，每一个下标元素是跟哪一个下标的元素有依赖的
5. 遍历顺序
   1. 从左到右
   2. 从上到下

2.4 精简化DP

在dp的过程中，有些问题的dp数组的空间结构可以进行优化，找到依赖关系进行优化，常见的有：

1. 滚动数组的优化
2. 斜率优化

3. 原则

3.1 递归设计的原则

1. 每一个可变参数的类型，一定不要比 int 类型更加复杂
2. 原则1可以违反，让类型突破到一维线性结构，那必须是唯一可变参数
3. 如果发现原则1被违反，但不违反原则2，只需要做到记忆化搜索即可
4. 可变参数的个数，能少则少

3.2 尝试模型

1. 从左往右的尝试模型
2. 范围上的尝试模型
3. 多样本位置全对应的尝试模型
4. 寻找业务限制的尝试模型

4. 总结

1. 设计暴力递归：重要原则 + 4 种常见尝试模型 见3
2. 分析有没有重复解
3. 用记忆化搜索 -> 用严格表结构实现动态规划：见2.3
4. 看看能否继续优化：见2.4

• ← Previous Post
• Next Post →