算法思想（二）：贪心、动态规划

贪心

• 适用范围（典型场景）：
  针对一组数据，我们定义了限制值和期望值，希望从中选出几个数据，在满足限制值的情况下，期望值最大。

• 尝试用贪心算法解决：

  每次选择当前情况下，在对限制值同等贡献量的情况下，对期望值贡献最大的数据。

• 举例验证结果是否是最优：

  大部分情况下，举几个例子验证一下就可以了，严格地证明贪心算法的正确性，是非常复杂的，需要涉及比较多的数学推理。

动态规划

适用范围（典型场景）：

问题符合 一个模型三个特征 可以用动态规划方法解决。

• 一个模型，即 多阶段决策最优解模型

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

• 三个特征

  • 最优子结构
    • 可以通过子问题的最优解，推导出问题的最优解；
    • 后面阶段的状态可以通过前面阶段的状态推导出来。
  • 无后效性
    • 解决问题某阶段状态一旦确定，就不受之后阶段的决策影响。
  • 重复子问题
    • 不同的决策序列，到达某个相同的阶段时，可能会产生重复的状态用同样的方式解决。

解题思路

• 明确状态
  • 可以先尝试用回溯法解决问题，画出简单的递归树，以此来寻找重复子问题
  • 递归树的每个节点表示一个状态和 N 个变量
• 明确选择
  • 每次决策选择最优的状态变量
• 确定 base case
  • 当问题数据规模最小的时候，base case 是显而易见的，可以直接得出结果的
• 写出递归方程
  • 根据状态定义和选择条件写出递归方程

代码模板

明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义：

# 初始化 base case
dp[0][0][...] = base
# 进行状态转移
for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 求最值(选择1，选择2...)

总结

我解动态规划问题一般会把原问题数据规模缩小，然后逐步增加数据规模，通过具体的实例来思考问题，找到问题的规律，就像上一篇 零钱兑换问题 的题解一样，根据找到的规律总结出 状态转移表 ，写出一般的 DP 之后，再考虑状态转移表的压缩问题，进行空间复杂度的优化。

动态规划问题的一般就是求最值问题。首先也是找每个阶段 重复子问题，从子问题找的 最优子结构，这样才能通过子问题的最值得到原问题的最值。每个重复子问题都包含相同结构的 状态 ，我根据已知的最简单的子问题的解 base case，自底向上逐步扩大规模，根据 **状态转移方程 **逐步得到原问题的解。动态规划问题基本都可以用回溯来解决，只不过回溯算法解决起来效率比较低，时间复杂度是指数级的，而动态规划执行效率要高很多。

贪心算法可以理解为一种特殊的动态规划问题，贪心选择具有特殊的性质，但可以有严格的数学证明，通过每阶段的最优选择来降低动态规划算法的时间复杂度。