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

LeetCode 55

本题可以使用动态规划解决。动态规划主要有四个步骤：

使用递归回溯方法
使用备忘录方法优化（自顶向下的动态规划）
消除递归方法（自底向上的动态规划）
使用其他方法优化时间/空间复杂度

首先使用递归回溯方法。以数组[2,3,1,1,4]为例，第一个数为2，意味者可能走的步数为1和2，此时做一个循环，针对每一个index，使用回溯法，计算所有情况，到达最后一个index时，返回True。此方法时间复杂度很高，代码在本题不会通过。

    class Solution:
        def canJump(self, nums):
            return self.canJumpFromPosition(0, nums)

        def canJumpFromPosition(self, pos, nums):
            if pos == len(nums) - 1:
                return True
            furthest =  min(pos + nums[pos], len(nums) - 1)
            for next_pos in range(pos + 1, furthest + 1):
                if self.canJumpFromPosition(next_pos, nums):
                    return True
            return False

第二步，使用备忘录法优化。上一种方法遍历所有的index，事实上有些index根本无法到达最后一个index。以数组[2, 4, 2, 1, 0, 2, 0]为例，其中index 2、3和4最终无法到达终点，那么我们可以使用备忘录排除这些index的再次遍历。备忘录初始化时，最后一个index定义为True，因为自身当然能到达自身，其他index定义为None。再修改回溯算法，判断当前index是否已知，直接返回Ture和False。其他方法相同。不过这种方法仍然会超时。

    class Solution:
        def canJump(self, nums):
            memo = [None] * len(nums)
            memo[-1] = True
            return self.canJumpFromPosition(0, nums, memo)

        def canJumpFromPosition(self, pos, nums, memo):
            if memo[pos]:
                return memo[pos]

            furthest =  min(pos + nums[pos], len(nums) - 1)
            for next_pos in range(pos + 1, furthest + 1):
                if self.canJumpFromPosition(next_pos, nums, memo):
                    memo[pos] = True
                    return True

            memo[pos] = False
            return False

第三步我们要消除递归，使用自底向上的动态规划算法，从数组右侧开始遍历。很可惜，这种方法还是会超时。

    class Solution:
    def canJump(self, nums):
        memo = [None] * len(nums)
        memo[-1] = True
        for pos in range(len(nums) - 2, -1, -1):
            furthest =  min(pos + nums[pos], len(nums) - 1)
            for j in range(pos + 1, furthest + 1):
                if memo[j] == True:
                    memo[pos] = True
                    break
        return memo[0] == True

在前三步仍无法解决超时的情况下，需要进行第四步做最后的优化。观察上一步代码，对于给定的pos，实际上我们需要寻找的是后面最左侧可行的位置。如果我们持续追踪这个最左侧位置的话，我们就可以避免二次搜索。一开始设置数组最后一个值为最左侧可到达的index，从右至左遍历，对于每个位置我们检查它能否到这个index。如果可到达，那么当前位置也是可行的，最左侧可到达index会变成当前位置。依次类推，如果遍历完成后最左侧可到达index是数组第一个数时，意味者它可从第一个位置到达最后一个位置。这个思想也是贪心算法的一个体现，代码中的left_index即为局部最优解，循环完毕后产生全局最优解。

    class Solution:
        def canJump(self, nums):
            left_index = len(nums) - 1
            for pos in range(len(nums) - 1, -1, -1):
                if pos + nums[pos] >= left_index:
                    left_index = pos
            return left_index == 0

LeetCode 300

链接：Longest Increasing Subsequence

本题求的是最长递增子序列（LIS），是一道经典问题。一种最简单的求解方式是使用暴力法遍历所有的子序列，并判断它们是否是LIS。我们需要降低时间复杂度，使用动态规划思想分析。观察后发现前i项的求得的LIS不受后面数据的影响。所以，如果我们知道截至第i项的所有LIS，再求前i+1项的LIS时，就可以使用前面数据的LIS，根据第i+1项数据的情况计算LIS。以数组[10,9,2,5,3,7,101]为例，定义dp[i]为前i项LIS，可得：

[10]，dp[1]=1
[10,9]，9<10，dp[2]=1
[10,9,2]，dp[3]=1
[10,9,2,5]，2<5，dp[4]=2
[10,9,2,5,3]，2<3，dp[5]=2
[10,9,2,5,3,7]，2<3<7，dp[6]=3
[10,9,2,5,3,7,101]，2<3<7<101，dp[6]=4

dp数组的最大值即为给定数组的最长递增子序列。

    class Solution:
        def lengthOfLIS(self, nums):
            if not nums:
                return 0
            dp = [1] * len(nums)
            for i in range(1, len(nums)):
                for j in range(i):
                    if nums[j] < nums[i]:
                        dp[i] = max(dp[i], dp[j] + 1)
            return max(dp)

因为使用了两层循环，所以算法的时间复杂度为O(n^2)。一种降低时间复杂度的方法是使用二分搜索算法。在这种方法中，dp数组用来存储当前的LIS。遍历时，用二分搜索算法查找当前值在数组中的位置，如果当前值小于数组的某个数组，则替换之。否则，将当前值添加进数组中。还是以上文的数组[10,9,2,5,3,7,101]为例，遍历可得：

[10]，添加10
[9]，9替换10
[2]，2替换9
[2,5]，添加5
[2,3]，3替换5
[2,3,7]，添加7
[2,3,7,101]，添加101

dp数组的最终长度即为最长递增子序列的长度。有时最终的dp数组未必是最长递增子序列，但长度是相同的。在Java中，Arrays类的binarySearch()方法提供了二分搜索法，Python也有这种方法，在bisect模块。具体用法见参考资料。bisect_left方法搜索数据n在数组dp中的位置，如果n已存在，则返回n的index。

class Solution:
    def lengthOfLIS(self, nums):
        import bisect
        dp = []
        for n in nums:
            if not dp or n > dp[-1]:
                dp.append(n)
            else:
                pos = bisect.bisect_left(dp, n)
                if pos == len(dp):
                    dp.append(n)
                else:
                    dp[pos] = n
        return len(dp)

参考资料： LeetCode 55题解 LeetCode 300题解花花酱 LeetCode 300 最长递增子序列 Python模块：bisect二分算法模块

LeetCode 55#

LeetCode 300#

LeetCode 55

LeetCode 300