Leetcode初级算法 打家劫舍（动态规划）（Python实现）
问题描述：
算法思想：
该问题的内在逻辑结构依然是动态规划里的经典结构。最关键的是推出状态转移方程，当前规模的对应解法由更低规模的解法，仿佛拾级而上，站在前人的肩膀上不断攀登。
实际操作起来，比较实用的方法如下：固定一个比较小的规模n， 进行思维实验。
例子：
nums = [2,7,9,3,1]，求这个数组对应的最高金额。
我们要做的是拿着某个规模的解，去求更高规模的解。用数组memo记录每个规模对应的解（最高金额），memo[i]对应的是nums的子数组nums[:i]（子问题）对应的解（最高金额）。这个过程就是从左向右顺序扫描nums数组，一边扫描一边将求出的解存储为memo[i]。假定现在扫描到i = 3，此时子数组为nums[:3] = [2,7,9]，我们来手算一下memo，得到memo[:3] = [2, 7, 11]。
好了，现在扫描到nums下一项，i = 4，nums[:4] = [2,7,9,3]，现在我们来求memo的第四项，也就是下一规模的解。对应这第四个屋子（nums[3] = 3），作为一个贼我们有两个选择：偷或是不偷。如果我没有偷第三家屋子，那就不用担心偷第四家会触发报警，那就放心偷好了；如果我偷了第三家，那就要斟酌一下偷不偷第四家了。偷第四家就必定要放弃第三家，但如果第四家钱特别多，那还是不亏的。i = 3时我们的选择是偷2 和 9，收益是11；i = 4时，如果偷3就只能 7+3，收益是10，不划算，果断不偷。memo更新为[2,7,11,11]。
类似地，继续扫描，i = 5，nums[:5] = [2,7,9,3,1],还是那个问题——这家屋子偷还是不偷。因为我们放弃了第四家，不存在相邻问题，放心偷就好。
发现规律了吗？下一规模的解，也就是memo[n]，要么是memo[n-1] （不偷，保持原状），或是memo[n-2]+nums[n]（放弃上一家，偷这家）。由于程序不知道上一家有没有偷，我们两个选择都算一下，取较大值即可。
代码：
class Solution(object):
def rob(self, nums):
“””
:type nums: List[int]
int
“””
if nums == []: return 0
n = len(nums)
if n == 1: return nums[0]
memo = [nums[0] for i in range(n)]
memo[1] = max(nums[:2])
for i in range(2,n):
choice1 = memo[i-1]
choice2 = memo[i-2]+nums[i]
memo[i] = max(choice1,choice2)
return memo[n-1]
左手的ㄟ右手
╰半夏微凉°
小鱼儿
Bertha 。
刺骨的言语ヽ痛彻心扉
╰+攻爆jí腚メ
还没有评论，来说两句吧...