动态规划

从0-1背包问题开始

对于一组不同重量、不可分割的物品，我们需要选择一些装入背包，在满足背包最大重量限制的前提下，背包中物品总重量的最大值是多少呢？

---

引入物品价值这一变量。对于一组不同重量、不同价值、不可分割的物品，我们选择将某些物品装入背包，在满足背包最大重量限制的前提下，背包中可装入物品的总价值最大是多少呢？

动态规划理论

“一个模型三个特征”理论

• 一个模型：多阶段决策最优解模型
• 三个特征：最优子结构、无后效性、重复子问题

多阶段决策最优解模型

我们一般是用动态规划来解决最优化问题，而这类问题包含以下特点：

• 求解的过程需要经历多个决策阶段；
• 每个决策阶段都对应着一组状态；
• 问题的求解是要寻找一组决策序列，经过这组决策序列能够产生最终期望的最优值。

最优子结构

最优子结构指的是问题的最优解包含子问题的最优解。

结合多阶段决策最优解模型来说，就是后面阶段的状态可以通过前面阶段的状态推导出来。

无后效性

无后效性是一个非常“宽松”的要求，一般只要满足多阶段决策最优解模型，就会满足无后效性。

它有两层含义：

1. 在推导后面阶段的状态的时候，我们只关心前面阶段的状态值，而不关心这个状态具体的推导过程。
2. 某阶段状态一旦确定，就不受之后阶段的决策影响。

重复子问题

不同的决策序列，到达某个相同的阶段时，可能会产生重复的状态。

两种求解思路

状态转移表法

回溯算法实现 → 定义状态 → 画递归树 → 找重复子问题 → 画状态转移表 → 根据递推关系填表 → 将填表过程翻译成代码

状态转移方程法

找最优子结构 → 写状态转移方程 → 将状态转移方程翻译成代码

贪心、回溯、分治与动态规划的比较

• 贪心算法实际上是动态规划算法的一种特殊情况。 它需要满足“贪心选择性”，即通过每轮选择局部最优解，能产生全局最优解。
• 回溯算法是个“万金油”，基本上能用的动态规划、贪心解决的问题，都可以用回溯算法解决。 回溯算法相当于穷举搜索，所以时间复杂度非常高，是指数级别的； 而回溯加“备忘录”的方法可以用来避免重复子问题，从执行效率上来讲跟动态规划没有差别。
• 分治算法尽管也能解决最优化问题，但大部分都不能抽象成多阶段决策模型。

LeetCode例题 120 (opens new window)

Triangle（三角形最小路径和）

思路：使用O(n)的额外空间（n为三角形的总行数），自下往上更新dp数组。

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        vector<int> dp(triangle.size() + 1, 0);
        for (int i = triangle.size() - 1; i >= 0; --i) {
            for (int j = 0; j <= i; ++j) {
                int min = dp[j] < dp[j+1] ? dp[j] : dp[j+1];
                dp[j] = min + triangle[i][j];
            }
        }
        return dp[0];
    }
};