算法思想(二):贪心、动态规划

贪心

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

  • 尝试用贪心算法解决:

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

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

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

动态规划

适用范围(典型场景):

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

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

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

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

解题思路

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

代码模板

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

1
2
3
4
5
6
7
# 初始化 base case
dp[0][0][...] = base
# 进行状态转移
for 状态1 in 状态1的所有取值:
for 状态2 in 状态2的所有取值:
for ...
dp[状态1][状态2][...] = 求最值(选择1,选择2...)

总结

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

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

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

坚持原创技术分享,您的支持将鼓励我继续创作!