浅谈动态规划Ⅱ

编程算法

字数统计: 2.7k阅读时长: 11 min

 2020/06/13   Share

前言

上次简单讲了动态规划的概念与如何分析，本篇文章就理一理几道常见的典型的动态规划题目。

实践

接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
来自leetcode 42题。
这道题目有两种大思路，一种是按行求，一种是按列求。由于我们只讨论动态规划，并且让理解相对简单，我们使用按列求该列可盛多少水。
首先，我们要明白，对于某一列，它能盛多少水在于它左右两边的最大柱子，而这列能盛的水，就是两边最高柱子中的较小者减去当前列的高度。
例如[0,1,0,2]这个高度数组，我们求下标为2的列能盛多少水。首先它左边最高的高度是1，右边最高的高度是2，所以它能盛的水就是min(1,2) - 0，也就是能盛1个高度的水。
由此我们便可以用暴力法解决这个问题。遍历每一个列时，分别求它左右最高的列，然后将结果加上min(maxleft,maxright) - height[i]。但使用暴力法的时间复杂度为O(N^2)，有可能会超时。

这时使用态规划来降低时间复杂度，典型地使用空间换取时间，我们设置maxleft与maxright数组，maxleft[i]表示i左边最高的高度，maxright类似，然后对整个高度数组先进行两次遍历，状态转移方程也很简单，maxleft[i] = max(height[i],maxleft[i-1]) 与 maxright[j] = max(height[j],maxright[j+1])，一个从左往右，一个从右往左。之后便和暴力法的思路一致。

接下来我们优化空间，我们使用双指针分别在高度数组的两侧，maxleft与maxright分别初始化为左右两侧高度，然后开始循环，条件为left<=right，此时我们便可开始求maxleft与maxright，取小的那一边，让结果加上min(maxleft,maxright)减去height[left] 或者 height[right]，取决于maxleft小还是maxright小。
由此我们便将时间复杂度降为O(N),空间复杂度降为O(1)。
下面是完整的双指针解法

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height: return 0
        n = len(height)

        left,right = 0, n - 1  
        maxleft,maxright = height[0],height[n - 1]
        ans = 0

        while left <= right:
            maxleft = max(height[left],maxleft)
            maxright = max(height[right],maxright)
            if maxleft < maxright:
                ans += maxleft - height[left]
                left += 1
            else:
                ans += maxright - height[right]
                right -= 1

        return ans

爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。
来自leetcode 70题
这道题目使用动态规划是十分好理解的，从前往后或者从后往前都可以。
首先这道题目的状态转移方程十分容易想到。举个例子来说明，假设fx表示爬到x阶的方案数量，那么到达这一层只能是从下一阶爬一阶，或者是下两阶爬两阶。那么状态转移方程就是fx = f(x-1) + f(x-2)。那么就可以得出代码，注意这是从前往后

class Solution:
    def climbStairs(self, n: int) -> int:
        
        if n == 1:
            return 1
        dp = [0 for _ in range(n+1)]
        dp[1] = 1
        dp[2] = 2
        for i in range(3,n+1):
            dp[i] = dp[i-1] + dp[i-2]
        return dp[-1]

当然我们可以假设从0级到0级也有一种方案，那么就可以从下标为2的数组开始遍历。
由于dp[i] = dp[i-1] + dp[i-2],只和前两项有关，那么我们便可以使用三个变量替换dp数组，使用滚动数组思想将空间复杂度降至O(1)

class Solution:
    def climbStairs(self, n: int) -> int:
        
        i = j = 0
        k = 1
        for i in range(1,n+1):
            i = j
            j = k
            k = i + j
        return k

其实这个状态转移方程就是斐波那契数列，他是有通项公式的，即

1 2	double sqrt5 = Math.sqrt(5); double fibn = Math.pow((1 + sqrt5) / 2, n + 1) - Math.pow((1 - sqrt5) / 2, n + 1);

并且时间复杂度为O(logN)，即pow的时间，如果n过大，带入通项公式时间会更短。

打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。
来自leetcode 198题
这道题很有意思，现在当小偷都需要高智商了。(笑)
这题思路也很简单，状态转移方程也容易想到，我们用dp[i]表示偷窃到的金额，那么dp[i] = max(dp[i-1],dp[i-2]+nums[i])，其中边界条件为dp[0] = nums[0],dp[1] = max(nums[0],nums[1])。
完整代码如下：

class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:
            return 0
        n = len(nums)
        if n <= 2:
            return max(nums)
        
        dp = [0 for _ in range(n)]
        dp[0] = nums[0]
        dp[1] = max(nums[1],nums[0])

        for i in range(2,n):
            dp[i] = max(dp[i-2]+nums[i],dp[i-1])
        return dp[-1]

由于dp[i]只与dp[i-1]还有dp[i-2]有关，python中可以使用两个变量来替代。

class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:
            return 0
        n = len(nums)
        if n <= 2:
            return max(nums)
        
        first, second = nums[0], max(nums[0], nums[1])
        for i in range(2, n):
            first, second = second, max(first + nums[i], second)
        
        return second

鸡蛋掉落

你将获得 K 个鸡蛋，并可以使用一栋从 1 到 N 共有 N 层楼的建筑。每个蛋的功能都是一样的，如果一个蛋碎了，你就不能再把它掉下去。你知道存在楼层 F ，满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎，从 F 楼层或比它低的楼层落下的鸡蛋都不会破。每次移动，你可以取一个鸡蛋（如果你有完整的鸡蛋）并把它从任一楼层 X 扔下（满足 1 <= X <= N）。你的目标是确切地知道 F 的值是多少。无论 F 的初始值如何，你确定 F 的值的最小移动次数是多少？
来自leetcode 887题
这道题目是十分经典的动态规划题目。
我们先定义状态:
dp[i][j]表示有i层楼梯时，使用j个鸡蛋的最少实验次数。
接着我们开始推导状态转移方程：
我们假设我们在k层扔鸡蛋，其中1<=k<=i，
· 如果鸡蛋破碎，那么就说明我们要在k层以下做这个实验，那么实验次数就变为dp[k-1][j-1].
· 如果鸡蛋没碎，那么我们可以去k层以上做这个实验，因此F的值就为dp[i-k][j]。
所以，dp[i][j]应该是这两个子问题的较大者加上1，再取1<=k<=i区间中的最小值。即dp[i][j] = min(1<=k<=i)(max(dp[k-1][j-1],dp[i-k][j]) + 1).
给出代码：

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:

        dp = [[9999 for j in range(K+1)] for i in range(N+1)]

        # 楼层为0时都为0
        for j in range(K+1):
            dp[0][j] = 0
        
        # 楼层为1时，0个鸡蛋扔0次，1个以上鸡蛋扔1次
        dp[1][0] = 0
        for j in range(1,K+1):
            dp[1][j] = 1
        
        # 鸡蛋为0时 全都为0
        # 鸡蛋为1时 等于楼层高度
        for i in range(N+1):
            dp[i][0] = 0
            dp[i][1] = i
        
        for i in range(2,N+1):
            for j in range(2,K+1):
                for k in range(1,i+1):
                    dp[i][j] = min(dp[i][j],max(dp[k-1][j-1],dp[i-k][j]) + 1)
        
        return dp[-1][-1]

这段代码的时间复杂度为O(N^2K)，即三层的循环，在数据量较大的情况下会超时，优化的关键点在于要找到1<=k<=i区间中的那个最小值。我们可以使用二分查找改写上面代码：

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:

        dp = [[9999 for j in range(K+1)] for i in range(N+1)]

        # 楼层为0时都为0
        for j in range(K+1):
            dp[0][j] = 0
        
        # 楼层为1时，0个鸡蛋扔0次，1个以上鸡蛋扔1次
        dp[1][0] = 0
        for j in range(1,K+1):
            dp[1][j] = 1
        
        # 鸡蛋为0时 全都为0
        # 鸡蛋为1时 等于楼层高度
        for i in range(N+1):
            dp[i][0] = 0
            dp[i][1] = i
        
        for i in range(2,N+1):
            for j in range(2,K+1):
                left = 1
                right = i
                while left + 1 < right:
                    mid = (left + right) // 2
                    if dp[mid-1][j-1] > dp[i-mid][j]:
                        right = mid
                    else:
                        left = mid
                
                dp[i][j] = max(dp[left-1][j-1],dp[i-left][j]) + 1
        
        return dp[-1][-1]

为什么判断条件是dp[mid-1][j-1] > dp[i-mid][j]?其实是因为dp[mid-1][j-1]代表着鸡蛋碎之后的F值，dp[i-mid][j]则是鸡蛋没碎的F值，如果鸡蛋碎了，那么下次应该在左边查找，所以right=mid-1，同理，如果鸡蛋没碎，我们应该提高楼层，让left = mid，去搜索右区间。
尽管复杂度已经降至O(NKlogN)，但上述代码在python中依旧是超时的。在java中是没有问题的，当然理解了思想使用什么语言都是一样的。（解释器语言不好混）

这里我们看看官方的解法：

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        memo = {}
        def dp(k, n):
            if (k, n) not in memo:
                if n == 0:
                    ans = 0
                elif k == 1:
                    ans = n
                else:
                    lo, hi = 1, n
                    # keep a gap of 2 X values to manually check later
                    while lo + 1 < hi:
                        x = (lo + hi) // 2
                        t1 = dp(k-1, x-1)
                        t2 = dp(k, n-x)

                        if t1 < t2:
                            lo = x
                        elif t1 > t2:
                            hi = x
                        else:
                            lo = hi = x

                    ans = 1 + min(max(dp(k-1, x-1), dp(k, n-x))
                                  for x in (lo, hi))

                memo[k, n] = ans
            return memo[k, n]

        return dp(K, N)

官方解法其实是差不多的，思路一致，改用递归加备忘录实现，速度上较快。

总结

今天总结了4道动态规划的题目，重新学习了这4道题目后感觉又学到了不少，对于扔鸡蛋的问题，这道题目是十分经典的，之后可能还会对这道题目进行深入探究。
下次再整理几道题目吧。

原文作者：Zer0e

原文链接：https://re0.top/2020/06/13/dp2/

发表日期：六月 13日 2020, 4:10:00 下午

更新日期：June 13th 2020, 11:03:03 pm

Next Post

浅谈高并发引起的问题
Previous Post

TopK问题与快速选择算法

CATALOG

1. 前言
2. 实践
3. 总结

