⚠️ 全是负数的时候
数组是 [-3, -1, -4],全都是负数。一边把 best 初始化成第一个元素,一边初始化成 0。运行下面这段程序: def max_sub(a): best = a[0] cur = a[0] for x in
把初始化写对
补全 max_sub:best 和 cur 都从第一个元素开始,循环从第二个元素起。对 [-3, -1, -4] 输出结果。
⚠️ 两种初始化一起跑
把两个版本都写出来:一个 best = a[0],一个 best = 0。对 [-3, -1, -4] 各跑一遍,把两个结果拼起来输出(正确的在前)。
爬楼梯的三个边界
补全 climb,然后算 n = 0、1、2 三种情况,把三个走法数拼起来输出。
⚠️ 三个边界一起验
一次验三种边界情况: 最大子段和,数组 [-3, -1, -4] 全是负数 爬楼梯,n = 0 打家劫舍,空数组 三个结果用 / 拼起来输出。
这三个经典题的共同点
爬楼梯、打家劫舍、最大子段和的共同点是【0】。
打家劫舍的转移里在选什么
打家劫舍的转移方程,每一步在决定【0】。
爬 10 级和爬 20 级
楼梯从 10 级加到 20 级,走法数会变成多少?运行下面这段程序: def climb(n): dp = [0] * (n + 1) dp[0] = 1 for i in range(1, n + 1):
另外两个经典题的答案
打家劫舍 [2, 7, 9, 3, 1]、最大子段和 [-2, 1, -3, 4, -1, 2, 1, -5, 4]。运行下面这段程序: def rob(a): dp = [0] * (len(a) + 1) if a:
爬楼梯:只用两个变量
补全 climb_roll:不开表,只用两个变量滚着往前推。输出爬 10 级的走法数。