使用(0, i]这种定义的时间复杂度为何会是O(n)级别的复杂度而不是(i, n-1]的O(n^2)

Question

class Solution(object):
    def rob(self, nums):
        length = len(nums)
        memo = [0 for index in range(length)]
        if length == 0:
            return 0
        elif length == 1:
            return nums[0]
        elif length == 2:
            return max(nums[0], nums[1])
        memo[0] = nums[0]
        memo[1] = nums[1]
        memo[2] = memo[0] + nums[2]
        for x in range(3, length):
            memo[x] = max(memo[x - 2], memo[x - 3]) + nums[x]
        return max(memo[length - 1], memo[length - 2])

代码是这样的，同样是动态规划，状态的定义不同为何会影响算法的时间复杂度，还是说定义为(i, n-1]的状态还有更好的写法。谢谢老师

Answer 1

liuyubobobo 2017-06-15 01:41:59

非常非常赞！

事实上，使用你的思路，很容易写出使用[i,n)的定义，且复杂度为O(n)级别的代码。我直接修改你的python代码，具体如下：

class Solution(object):
    def rob(self, nums):
        length = len(nums)
        memo = [0 for index in range(length)]
        if length == 0:
            return 0
        elif length == 1:
            return nums[length-1]
        elif length == 2:
            return max(nums[length-1], nums[length-2])
        memo[length-1] = nums[length-1]
        memo[length-2] = nums[length-2]
        memo[length-3] = memo[length-1] + nums[length-3]
        for x in reversed(range(0,length-3)):
            memo[x] = max(memo[x + 2], memo[x + 3]) + nums[x]
        return max(memo[0], memo[1])

仔细思考，实际上，是这个思路的状态转移过程和课程中讲的略有不同。以你的[0,i]定义为例。课程中的思路是，如果选取第i个元素，就要检查这第i个元素和之前的那种盗取策略匹配，而这个检查检查了从memo[0]到memo[i-2]的所有可能。但是，根据我们的状态定义，memo[x]中存储的并不是“一定”要偷取第x个房子，而是考虑[0...x]中所有房子的结果。所以其实我们没必要搜索从memo[0]到memo[i-2]的所有可能，memo[i-2]中就蕴含了这个最大值。

备课的时候太沉浸在将组合问题的动态规划结构，忽略了这个最优子性质。非常抱歉。感谢你的好问题。有时间可以加我的微信：liuyubobobo。我会发给你一个小红包：）

• 提问者 Flight0 #1

  谢谢老师，我懂了