动态规划问题的思路和技巧

关注

发布于: 2020 年 05 月 03 日

动态规划是算法中最常见的一类问题之一，其解题思路常常为，将大问题分解为小问题，并且建立起通过解决小问题到解决大问题的对应关系来得到最终的答案，一旦找了分解问题和合并小问题答案的方程，问题本身就迎刃而解。然而，对于具体实现来说，从找到对应关系到最优的实现方式之间往往有着一些小技巧，这篇文章主要展开讲讲如何用一套思维模式和技巧来解决优化大部分动态规划的问题。我们以 leetcode 上这道 easy 的动态规划题https://leetcode.com/problems/house-robber/为例子来层层剖析如何切入这种类型的题目。

问题分解

由于强盗不能抢相邻的两间房子，那么对于任意一间房子 i 而言，强盗要么

抢当前的，然后跳过 i+1 间房子
不抢当前的房子，然后抢 i+1 间房子

也就是说，对于任意一间房子 i 来说，强盗都有两个选择，并且每次选择都会影响后面的选择和结果，这是动态规划题目一个非常典型的特征，每次决策都对下一次决策参加影响，对最后的结果起作用。那对于这个抢房子的问题来说，我们已经将这个大问题分解成了小问题，让 dp(i)代表，当强盗从第 i 个房子开始抢，他能得到的最大收益，那么存在下面等式

dp(i) =  max(dp(i+2)+house_value[i], dp(i+1))

复制代码

递归

当我们找到了问题分解之后的对应关系后，最简单的实现方式就是递归了

func rob(nums []int) int {    return helper(nums, 0)}func helper(nums []int , i int) int {    if i > len(nums) - 1 {        return 0;    }    //max(robbery current, skip current)    return max(helper(nums, i+2)+nums[i], helper(nums, i+1))}

复制代码

memorization

递归是最简单的实现方式，不过上述的实现方式浪费了很多时间在重复计算上面，动态规划问题可以通过 memorization 的方式来实现优化。memorization 就是用字典或者数组来记住计算过的结果来避免重复计算、提高速度，比较典型的应用就是斐波那契数列。

func rob(nums []int) int {    dp = make([]int, len(nums)+1)    for i := 0; i < len(dp); i++ {        dp[i] = -1    }    return helper(nums, 0)}func helper(nums []int , i int) int {    if i > len(nums)-1 {        return 0;    }    if dp[i] >= 0 {        return dp[i]    }    //max(robbery current, skip current)    val := max(helper(nums, i+2)+nums[i], helper(nums, i+1))    dp[i] = val    return val}

复制代码

循环

递归往往可以退化为循环的实现方式，虽然时间复杂度是一样的，但是循环避免了大量调用栈的创建和函数调用的开销，所以往往会快一些，而且在动态规划问题中来看，循环的实现方式更简介，因为动态规划问题的本质就是在前后状态有依赖的前提下来进行状态的推导。

func rob(nums []int) int {    if len(nums) == 0 {        return 0    }    dp = make([]int, len(nums)+2)    for i := len(nums)-1; i >= 0; i-- {        dp[i] = max(dp[i+2]+nums[i], dp[i+1])    }    return dp[0]}

复制代码

由于我们推导的公式是

dp(i) =  max(dp(i+2)+house_value[i], dp(i+1))

复制代码

所以，在 for 循环里面，我们是从数组的末尾开始到 index 为 0 为止，这也叫 top-down。另外一种是 down-top 的方式，假如 dp[i]代表的是当强盗当抢到第 i 个房子时，他已经得到的最大收益，那么存在下面的等式

dp(i) = max(dp(i - 2) + house_value[i], dp(i - 1))

复制代码

本质上两种方式是一样的，只是建模的思维不同而已，具体到代码实现上会体现为循环推导的方向不一样，down-top 则是从头开始，而不是从末尾。

func rob(nums []int) int {    if len(nums) == 0 {        return 0    }    dp = make([]int, len(nums)+2)    for i := 2; i < len(nums)+2; i++ {        dp[i] = max(dp[i-2]+nums[i-2], dp[i-1])    }    return dp[len(nums) +  1]}

复制代码

减少空间复杂度

动态规划问题往往会用一维数组或者矩阵来保存状态和进行状态推导，比如强盗问题中，我们用一维数组 dp 来实现 memorization，但是其实仔细分析我们会发现，我们只需要两个变量就可以了。

current =  max(prev2 + house_value[i], prev1)

复制代码

由于每次我们都只依赖两个状态，分别代表 dp[i-2] (或者 dp[i+2) 和 dp[i-1] （或者 dp[i+1])，那么我们就可以只用两个变量来优化我们的空间复杂度，然后每次循环让

   prev2 = prev1   prev1 = current

复制代码

迭代去更新这两个变量的值即可。

func rob(nums []int) int {    if len(nums) == 0 {        return 0    }    prev1, prev2, curr := 0,0, 0    for _, n := range nums {        curr = max(prev2 + n, prev1)        prev1, prev2  = curr, prev1    }    return curr}

复制代码

总结

总的来说，经过以上的步骤，我们最终可以以非常简洁的代码、低空间复杂度和时间复杂度来解决一个动态规划的问题。其实解决动态规划问题的关键就是找到问题分解之后的推导关系，剩下的实现部分就可以像上面一样一步步优化。

Reference

https://leetcode.com/problems/house-robber/discuss/156523/From-good-to-great.-How-to-approach-most-of-DP-problems

发布于: 2020 年 05 月 03 日阅读数: 209

原文链接:【http://xie.infoq.cn/article/0a2bad986c6e4602a2575ed8d】。文章转载请联系作者。

Kenn

关注

忘记密码记住我 2018.03.09 加入

Démon de Laplace

发布

暂无评论

创作场景

动态规划问题的思路和技巧

问题分解

递归

memorization

循环

减少空间复杂度

总结

Reference

Kenn

评论