使用(0, i]这种定义的时间复杂度为何会是O(n)级别的复杂度而不是(i, n-1]的O(n^2)
来源：9-4 状态的定义和状态转移 House Robber
Flight0
2017-06-14
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]的状态还有更好的写法。谢谢老师
写回答
1回答
-
非常非常赞！
事实上，使用你的思路，很容易写出使用[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。我会发给你一个小红包：）
1312017-06-16
相似问题