算法@LeetCode:HouseRobber

Log

• 【170422】完成 01 版提交（Python）
• 【170423】研究过参考答案并记录

题目

House Robber

【题目类型备注】

动态规划

提交

01

【语言】

Python

【时间】

170422

【思路】

（是按照「动态规划」的分类来查找题目的，因此直接思考如何用 DP 的思路来解题）

本问题可抽象为：

已知一个非负整数数列，求由其中任意若干不相邻的元素组成的数列的和，这个和是所有可能的数列的和里最大的。

假设我们已经知道了 n-1 规模的解，然后知道了第 n 个元素，如何求解 n 规模的问题？这里无非是要考虑

1. 是使用 nums[n] ，还是不使用 nums[n]？
2. 若使用 nums[n]，如何使用？

我们分情况考虑。假设我们用名为 answer 的数列存储答案，answer[n] 表示 n 规模的问题的答案

由于要求得到的新数列中各元素在原数列中的下标不能相邻，那么首先考虑简单的情况：若 answer[n-1] 未使用 nums[n-1]，那么必然有 answer[n] = answer[n-1] + nums[n]。理由是：在 n-1 规模的问题中，无论是使用了 nums[n-1] 的数列，还是那些未使用的数列，所有可能的数列的和都不如没有使用 nums[n-1] 的这个 answer[n-1] 来得大，因此它们再加上这个新的非负整数 nums[n]以后，一定不如 answer[n-1] + nums[n] 来得大。

那么若 n-1 规模的问题使用了 nums[n-1]，那么就要考虑下述 3 个和哪个更大：

1. answer[n-1]：在这种情况下，直接使用上一规模的最优解
2. answer[n-2] + nums[n]：在这种情况下，使用 n-2 规模的最优解加上 nums[n]
3. answer[n-1] - nums[n-1] + nums[n]：在这种情况下，使用 n-1 规模的最优解，去掉元素 nums[n-1] 再用上 nums[n]

于是很容易得到代码如下。

【代码】

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # if len(nums) < 3
        if len(nums) == 0:
          return 0
        if len(nums) == 1:
          return nums[0]
        if len(nums) == 2:
          return max(nums)
        # if len(nums) >= 3...
        if nums[1] >= nums[0]:
          answer = [nums[0], nums[1]]
          useLast = True
        else:
          answer = [nums[0], nums[0]]
          useLast = False

        i = 2
        while (i < len(nums)):
          # if or not use the last element
          if not useLast:
            answer.append(answer[i-1] + nums[i])
            useLast = True
          else:
            if (answer[i-1] >= answer[i-2]+nums[i]) and (nums[i-1] >= nums[i]):
              answer.append(answer[i-1])
              useLast = False
            else:
              if (answer[i-2]+nums[i] >= answer[i-1]-nums[i-1]+nums[i]):
                answer.append(answer[i-2]+nums[i])
                useLast = True
              else:
                answer.append(answer[i-1]-nums[i-1]+nums[i])
                useLast = True
            # add loop indicator
          i += 1

        return answer[len(nums)-1]

【结果】

运行时：39 ms

报告链接：https://leetcode.com/submissions/detail/100845278/

不知道其他拥有 LeetCode 帐号的人能不能看到该报告，所以顺便附图如下：

Your runtime beats 73.14% of python submissions.

00

参考解法：

• Python
• C

清晰的思路还是看 Python 那个参考解法里的状态方程。有一个很重要的点：我之所以写了 3 个比较，其实又是在思考状态方程时思路不对了：也就是说，对于位置 k 而言，只要比较 answer[k-1] 与 anwser[k-2] + nums[k] 两者之间的大小。

为什么不用再与使用了 nums[k-1] 的 answer[k-1] - nums[k-1] + nums[k] 比较？因为，answer[k-1] - nums[k-1] 后的答案，一定不会超过 answer[k-2]（这是由 answer 的定义决定的：answer[k] 表示长度为 k 的数列的最大和；不用 nums[k-1]，相当于人为把 k-1 规模的问题再缩小了 1 个规模，成了 k-2 规模，那么直接取 answer[k-2] 即可）

自己实现一遍最优解：

• [language]。。。