斐波那契数列问题

题目列表

Fibonacci Numbers

爬楼梯

偷房子

198. 打家劫舍

题解

Fibonacci Numbers

1. 509. 斐波那契数

2. 1137. 第 N 个泰波那契数

爬楼梯

1. 70. 爬楼梯

2. 746. 使用最小花费爬楼梯

偷房子

198. 打家劫舍

class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:
            return 0
        nums_length = len(nums)
        if nums_length == 1:
            return nums[0]
        
        dp = [0]*(nums_length+1)
        dp[1] = nums[0]
            
        for i in range(2,nums_length+1):
            dp[i] = max(dp[i-1], dp[i-2]+nums[i-1])
        return max(dp)

优化：max(dp)实际上就是最后一项可改为 dp[-1]
空间优化：只要求最大值，不必存储所有DP值
dp[i-1] 和 dp[i-2] 已经足够，用两个变量保存即可

空间优化示意图

class Solution:
    def rob(self, nums: List[int]) -> int:
        prev = 0    # dp[i-2]
        curr = 0    # dp[i-1]
        for i in nums:
            prev, curr = curr, max(curr, prev + i)
        # 循环结束时，curr 表示 dp[-1]，prev 表示 dp[-2]
        return curr

求最大值方案

不输出最大值，而是输出最大值方案。

修改DP数组，每个格子储存当前最优方案

每个格子储存当前最优方案

如果 f(k) = f(k-1)，那么 dp[k] 复制 dp[k-1] 的内容
如果 f(k) = f(k-2) + H_k-1，那么 dp[k] 复制 dp[k-2] 的内容，并追加元素 k-1（偷第 k-1k−1 号房子）。

from copy import deepcopy
def rob(nums):
    if not nums:
        return 0
    nums_length = len(nums)
    if nums_length == 1:
        return nums[0],[0]
    
    dp = [0]*(nums_length+1)
    path = [[]]*(nums_length+1)
    path[1] = [0]
    # path[2] = [0] if nums[0] > nums[1] else [1]
    # print(path)
    dp[1] = nums[0]
        
    for i in range(2,nums_length+1):
        if dp[i-1] > dp[i-2]+nums[i-1]:
            dp[i] = dp[i-1]
            path[i] = deepcopy(path[i-1])
        else:
            dp[i] = dp[i-2]+nums[i-1]
            path[i] = deepcopy(path[i-2])+[i-1]
        print(path)
    return dp[-1],path[-1]

print(rob([2,7,9,3,1]))

这样定义 DP 数组的话，算法的时间、空间复杂度都会升高。总体空间复杂度由O_(n)上升到 O_(n²) , 总体时间复杂度也会从O_(n)上升到 O_(n²)

优化：使用 back 数组
上一个方法构造 DP 数组时其实只用到 path[i-2] 和 path[i-1]，所以只用记录复制的关系就可以大幅度减少空间复杂度。

back 数组

DP 数组还是记录原始的「偷前 k 间房子的最大金额」
Back 数组中的值要么是 -1，要么是 -2。
如果 back[k] = -1，表示 dp[k] 由 dp[k-1] 计算而来；
如果 back[k] = -2，表示 dp[k] 由 dp[k-2] 计算而来。
最后从dp[n] 出发根据 back 数组从后往前查找，找到最优解的具体方案

# from copy import deepcopy
def rob(nums):
    if not nums:
        return 0
    nums_length = len(nums)
    if nums_length == 1:
        return nums[0],[0]
    
    dp = [0]*(nums_length+1)
    # path = [[]]*(nums_length+1)
    back = [0]*(nums_length+1)
    back[1] = -2
    # path[1] = [0]
    # path[2] = [0] if nums[0] > nums[1] else [1]
    # print(path)
    dp[1] = nums[0]
        
    for i in range(2,nums_length+1):
        if dp[i-1] > dp[i-2]+nums[i-1]:
            dp[i] = dp[i-1]
            back[i] = -1
            # path[i] = deepcopy(path[i-1])
        else:
            dp[i] = dp[i-2]+nums[i-1]
            back[i] = -2
            # path[i] = deepcopy(path[i-2])+[i-1]
    
    path = []
    i = nums_length
    while i > 0:
        if back[i] == -2:
            path.append(i-1)
        i += back[i]
    return dp[-1],path[::-1]

print(rob([2,7,9,3,1]))

213. 打家劫舍 II

问题变种，首尾相接成环形。也就是说不能同时偷头和尾（相邻的）

Reference

[1]动态规划只能用来求最值吗？
[2] leetcode动态规划题目总结
[3]力扣上的 DP 问题分类汇总

最后编辑于：2020.05.19 09:34:05