算法@LeetCode:HouseRobber
Log
- 【170422】完成 01 版提交（Python）
- 【170423】研究过参考答案并记录
题目
【题目类型备注】
动态规划
提交
01
【语言】
Python
【时间】
170422
【思路】
（是按照「动态规划」的分类来查找题目的，因此直接思考如何用 DP 的思路来解题）
本问题可抽象为：
已知一个非负整数数列，求由其中任意若干不相邻的元素组成的数列的和，这个和是所有可能的数列的和里最大的。
假设我们已经知道了 n-1 规模的解，然后知道了第 n 个元素，如何求解 n 规模的问题？这里无非是要考虑
- 是使用
nums[n]，还是不使用nums[n]？- 若使用
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 个和哪个更大：
-
answer[n-1]：在这种情况下，直接使用上一规模的最优解 -
answer[n-2] + nums[n]：在这种情况下，使用 n-2 规模的最优解加上nums[n] -
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 那个参考解法里的状态方程。有一个很重要的点：我之所以写了 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]。。。
