一周LeetCode习题精选——动态规划

LeetCode 198

本题使用动态规划解决。首先需要分析题目的递归关系：当强盗到达第i间房屋时，他可以选择抢，也可以选择不抢。如果抢劫这间房屋，根据题目要求，他必定没有抢劫第i-1间房屋，但他可能抢劫第i-2间房屋。如果不抢劫第i间房屋，那么他可能抢劫第i-1间房屋。这两个选择造成抢劫得来金钱的不同。设rob(i)为前i间房屋抢劫得来金钱的最大值，第一种需要计算前i-2间房屋抢劫金钱的最大值加上第i间房屋抢劫的金钱。第二种只需要计算前i-1间房屋抢劫金钱的最大值。两者需取其中最大值，由此得出递归关系：

rob(i) = max(rob(i - 2) + curr, rob(i - 1)) # curr代表当前第i间房屋抢劫的金钱

得出递归关系后可直接使用递归方法，不过普通的递归方法用在本题会超时：

    class Solution:
        def rob(self, nums):
            return self.rob_house(nums, len(nums) - 1)

        def rob_house(self, nums, i):
            if i < 0:
                return 0
            return max(self.rob_house(nums, i - 2) + nums[i], self.rob_house(nums, i - 1))

继续优化算法，采用备忘录法，备忘录法是自顶向下的算法，将求出的值保存在备忘录中，避免普通递归方法中的重复计算。定义一个值均为-1的数组，每次计算得出的结果存入数组中，如果某次递归发现memo[i]的值不为-1，说明已经保存之前计算的结果，直接返回memo[i]，无需再次计算。

    class Solution:
        def rob(self, nums):
            memo = [-1 for _ in range(len(nums))]
            return self.rob_house(nums, len(nums) - 1, memo)

        def rob_house(self, nums, i, memo):
            if i < 0:
                return 0
            if memo[i] != -1:
                return memo[i]
            memo[i] = max(self.rob_house(nums, i - 2, memo) + nums[i], self.rob_house(nums, i - 1, memo))
            return memo[i]

自底向上的动态规划，使用迭代方法。此方法和上一种方法均击败了94.83%的python3提交代码。

    class Solution:
        def rob(self, nums):
            if not nums:
                return 0
            memo = [-1 for _ in range(len(nums) + 1)]
            memo[0] = 0
            memo[1] = nums[0]
            for i in range(1, len(nums)):
                memo[i + 1] = max(memo[i - 1] + nums[i], memo[i])
            return memo[-1]

在上一种方法中，实际参与循环的只有memo[i]和memo[i-1]两项，所以该方法的空间可以进一步的压缩，使用两个变量来代替。其中prev2代表递归式中的nums[i-2]，prev1代表nums[i-1]，每次循环将prev2的值修改为上一次循环prev1的值，更新后prev1的值则类似于递归关系中的rob(i)。

    class Solution:
        def rob(self, nums):
            prev2 = prev1 = 0
            for n in nums:
                prev2, prev1 = prev1, max(n + prev2, prev1)
            return prev1

LeetCode 494

链接：Target Sum

本题可使用搜索或者动态规划。前者即使用DFS暴力搜索，计算所有可能的和差情况。另外使用备忘录方法可以减少时间复杂度。这里主要介绍动态规划。

我们定义Sum(i)为前i项数字所有可能的和差情况，则Sum(i-1)为前i-1项的和差情况，那么可以推出Sum(i-1)加nums[i]和减nums[i]分别是两种情况，即可得出递推关系

Sum(i) = (Sum(i-1) + nums[i]) + (Sum(i-1) - nums[i])

这里的Sum(i)可以用二维数组dp[i][j]来表示，i表示nums中的第i项数字，i等于0时不对应nums中的数字。j表示和差的结果，数组的值代表对于前i个数所能达到各个结果的次数。那么二维数组所需的空间又是多少呢？i的空间经上文分析可得为nums中数字的长度加1，j的空间我们来举例说明，假如数组为[1,1,1,1,1]，那么它的最大和为5，最小和为-5，空间为11，即是两倍的最大和加一。下面的视频推荐观看，作者解释的比较清晰。

以下为AC代码：

    class Solution:
        def findTargetSumWays(self, nums, S):
            from functools import reduce
            sum = reduce(lambda x, y: x+y, nums)
            if sum < S:
                return 0
            dp = [[0] * (sum * 2 + 1) for _ in range(len(nums) + 1)]
            dp[0][sum] = 1
            for i in range(len(nums)):
                for j in range(nums[i], 2 * sum + 1 - nums[i]):
                    if dp[i][j]:
                        dp[i + 1][j + nums[i]] += dp[i][j]
                        dp[i + 1][j - nums[i]] += dp[i][j]
            return dp[len(nums)][S + sum]

由于数组遍历中i+1只和i有关系，所以我们可以将二维数组降为一维。在i循环时建立一个新数组next，j循环时用next数组记录结果，结束后将next的值复制给dp。

class Solution:
    def findTargetSumWays(self, nums, S):
        from functools import reduce
        sum = reduce(lambda x, y: x+y, nums)
        if sum < S:
            return 0
        dp = [0 for _ in range(sum * 2 + 1)]
        dp[sum] = 1
        for i in range(len(nums)):
            next = [0 for _ in range(sum * 2 + 1)]
            for j in range(nums[i], 2 * sum + 1 - nums[i]):
                if dp[j]:
                    next[j + nums[i]] += dp[j]
                    next[j - nums[i]] += dp[j]
            dp = next
        return dp[S + sum]

参考资料：算法-动态规划 Dynamic Programming–从菜鸟到老鸟 LeetCode 494题解花花酱 LeetCode 494. Target Sum

LeetCode 198#

LeetCode 494#

LeetCode 198

LeetCode 494