Python一维动态规划
困难6一维动态规划：像记流水账一样解决最优化问题
你有没有想过，如果每天只能做一次选择，而且后面的决定会受到前面选择的影响，怎样才能做出最好的安排？一维动态规划就是专门解决这类问题的工具。它用一个一维数组（像一条线）来记录每一步的最优结果，然后一步步往后推，最终得到全局最优答案。
什么是一维动态规划？
简单来说，一维动态规划是“把大问题拆成小问题，每个小问题只依赖前面的一两个小问题”。就像你在操场上跑步，每一步踩到的位置（状态）只和上一步的位置有关，你只需要记住每一步踩哪里最好，然后传到下一步。
核心要素：
- 一维数组
dp：dp[i]表示“当问题规模为 i 时”或者“以第 i 个位置为结尾时”的最优解。 - 状态转移方程：从
dp[i-1]、dp[i-2]等已知状态，通过一个公式算出dp[i]。 - 初始条件：
dp[0]或dp[1]是多少需要先定好。
生活中的例子：买糖果（再详细一点）
假设你有一张零花钱计划表，每天可以买糖果，但妈妈定了一个规矩：
- 每天最多买 3 颗糖；
- 相邻两天不能都买（如果今天买了，明天就不能买）；
- 你想让一个月（30天）里买到的糖果总数最大。
这个问题就是一个典型的一维动态规划：
- 定义
dp[i]表示前 i 天（从第1天到第i天）能得到的最大糖果数。 - 那么对于第 i 天，有两种选择：
- 今天不买：那么
dp[i] = dp[i-1]（继承前一天的成果）。 - 今天买（并且前一天没买）：那今天买的数量可以是 1、2 或 3，但要保证前一天没买，所以
dp[i] = dp[i-2] + 今天买的糖数。
- 今天不买：那么
- 取两种选择中更大的值作为
dp[i]。 - 最后
dp[30]就是答案。
这种“从前面一天或两天推出当前”的思路，就是一维动态规划的精髓。
特征总结（记住三点）
- 状态是一维的：用数组下标 i 表示不同的阶段（位置、天数、长度等）。
- 转移是线性的：当前状态只依赖前面一个或两个状态，不会跳来跳去。
- 常见题型：最大子段和、最长递增子序列、打家劫舍、爬楼梯、零钱兑换等。
经典问题详解：最大子段和（带详细推理）
题目：给你一个整数列表，例如 [-2, 1, -3, 4, -1, 2, 1, -5, 4]，找出连续的一段（子数组），使其和最大。
比如 [4, -1, 2, 1] 的和是 6，就是答案。
为什么用一维动态规划？
因为“以某个位置结尾的最大子段和”只和“前一个位置结尾的最大子段和”有关。如果你已经知道了“以第 i-1 个数结尾的最大子段和”，那么要算“以第 i 个数结尾的最大子段和”时，只需要决定：是把第 i 个数接上去，还是单独重新开始。
状态定义
dp[i]表示以列表第 i 个元素（下标从0开始）为结尾的连续子数组的最大和。- 注意：
dp[i]不一定是全局最大，它只是“必须包含第 i 个元素”的最大值。
状态转移方程
dp[i] = max( nums[i], dp[i-1] + nums[i] )
解释：
- 如果
dp[i-1]是负数，加上它反而会变小，不如重新从nums[i]开始。 - 如果
dp[i-1]是正数，加上它能让总和更大。
边界条件
dp[0] = nums[0]，因为只有一个元素时，最大子段和就是它自己。
代码实现
def max_subarray_sum(nums):
n = len(nums) # 列表长度
if n == 0: # 空列表直接返回0
return 0
# dp[i] 表示以 nums[i] 结尾的最大子段和
dp = [0] * n # 初始化dp数组
dp[0] = nums[0] # 第一个元素作为起点
max_sum = dp[0] # 记录全局最大值
for i in range(1, n): # 从第二个元素开始遍历
# 关键转移：要么接上前面的子段，要么重新开始
dp[i] = max(nums[i], dp[i-1] + nums[i])
# 更新全局最大值
if dp[i] > max_sum:
max_sum = dp[i]
return max_sum
# 测试
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray_sum(arr)) # 输出6，对应子段 [4, -1, 2, 1]
手工推演一遍
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
| i | nums[i] | dp[i] 计算过程 | dp[i] |
|---|---|---|---|
| 0 | -2 | 初始值 | -2 |
| 1 | 1 | max(1, -2+1=-1) = 1 | 1 |
| 2 | -3 | max(-3, 1+(-3)=-2) = -2? 注意：1是dp[1]，-2 > -3，所以取-2 | -2 |
| 3 | 4 | max(4, -2+4=2) = 4 | 4 |
| 4 | -1 | max(-1, 4+(-1)=3) = 3 | 3 |
| 5 | 2 | max(2, 3+2=5) = 5 | 5 |
| 6 | 1 | max(1, 5+1=6) = 6 | 6 |
| 7 | -5 | max(-5, 6+(-5)=1) = 1 | 1 |
| 8 | 4 | max(4, 1+4=5) = 5 | 5 |
全局最大值在 i=6 时出现，为 6。对应子段从 i=3 到 i=6：[4, -1, 2, 1]。
另一个经典问题：打家劫舍（贴近生活）
题目：你是一个小偷，计划偷一条街上的房子。每间房子有不同金额的现金，但相邻的两间房子不能同时偷（会触发警报）。求你能偷到的最大金额。
比如金额列表 [2, 7, 9, 3, 1]，最优是偷第1、3、5家：2+9+1=12。
思考
- 定义
dp[i]表示前 i 间房子（0到i-1）能偷到的最大金额。 - 对于第 i 间房子（下标i-1），有两种选择：
- 不偷：
dp[i] = dp[i-1] - 偷：那么前一家（i-1）不能偷，所以
dp[i] = dp[i-2] + 当前房子的钱
- 不偷：
- 取较大值。
代码
def rob(nums):
n = len(nums) # 房子数量
if n == 0:
return 0
if n == 1:
return nums[0] # 只有一间直接偷
dp = [0] * n # dp[i] 表示偷前 i+1 间房的最大值
dp[0] = nums[0] # 只有一间房，偷它
dp[1] = max(nums[0], nums[1]) # 两间房，偷金额大的那间
for i in range(2, n): # 从第三间开始
# 偷当前这间 vs 不偷（继承前一间的最优）
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
return dp[n-1] # 最后一项就是答案
# 测试
houses = [2, 7, 9, 3, 1]
print(rob(houses)) # 输出12
新手常犯的错误
-
忘记初始化 dp[0] 和 dp[1]
很多一维DP问题需要明确前两个状态，比如打家劫舍中dp[0]和dp[1]都是手动设置的。如果只设了dp[0]，循环从 1 开始会出错。 -
混淆 dp[i] 的含义
最大子段和的dp[i]是“以 i 结尾的”，不是“前 i 个元素的最大值”。如果混淆，会导致转移公式写错。 -
没有考虑空列表或单个元素的情况
输入[]或[5]时，程序应该能正确处理，否则会索引越界。 -
忘记更新全局最优值
在最大子段和中，dp[i]只是局部最优，需要额外变量记录全局最大值，而不是最后取dp[n-1]。
完整可运行示例（含测试）
下面是一个完整的脚本，包含两个经典问题的实现和测试。
# 最大子段和
def max_subarray(nums):
n = len(nums) # 数组长度
if n == 0:
return 0
dp = [0] * n # dp[i] 表示以 nums[i] 结尾的最大子段和
dp[0] = nums[0] # 第一个元素
best = dp[0] # 全局最大子段和
for i in range(1, n):
dp[i] = max(nums[i], dp[i-1] + nums[i])
best = max(best, dp[i]) # 更新全局最优
return best
# 打家劫舍
def rob(nums):
n = len(nums)
if n == 0:
return 0
if n == 1:
return nums[0]
dp = [0] * n
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, n):
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
return dp[n-1]
# 测试
if __name__ == "__main__":
# 最大子段和测试
test_arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print("最大子段和:", max_subarray(test_arr)) # 6
# 打家劫舍测试
test_houses = [2, 7, 9, 3, 1]
print("打家劫舍最大金额:", rob(test_houses)) # 12
相关知识点延伸
学会一维动态规划后，你可以继续探索：
- 二维动态规划：类似一维，但用二维数组记录状态，比如走迷宫、背包问题。
- 最长递增子序列：一维DP的经典变种，需要两层循环。
- 状态压缩：如果只依赖前两个状态，可以用两个变量代替数组，节省空间（比如用
prev和curr）。 - 贪心算法：部分DP问题可以用贪心更快解决（比如最大子段和也有贪心解法），但DP更通用。
一维动态规划就像“搭积木”，一块一块垒起来，每一步都踩在前一块的肩膀上。只要抓住“状态定义”和“转移方程”，你会发现很多看似复杂的问题其实很简单。加油！
例题精讲
用一维动态规划求解爬楼梯问题（每次可以爬1阶或2阶，到达第n阶有多少种方法）。假设dp[i]表示到达第i阶的方法数，则正确的递推公式是？
在求解“最小花费爬楼梯”问题时，数组cost长度为n，dp[i]表示爬到第i阶（从0开始）的最小花费。通常初始化dp[0]和dp[1]为0（假设可以从起点免费到第0或第1阶），则正确的状态转移方程是？
一维动态规划的状态转移方向一定是从左到右（即从小索引到大索引）的。
下面是用一维动态规划计算斐波那契数列第n项（假设n>=1）的代码，请填写缺失部分。
def fib(n):
if n <= 2:
return 1
dp = [0] * (n+1)
dp[1] = dp[2] = 1
for i in range(3, n+1):
dp[i] = ___
return dp[n]下列代码使用一维动态规划（Kadane算法）求数组nums的最大子数组和，请填写缺失部分。
def maxSubArray(nums):
n = len(nums)
dp = [0] * n
dp[0] = nums[0]
max_sum = dp[0]
for i in range(1, n):
dp[i] = max(nums[i], ___)
if dp[i] > max_sum:
max_sum = dp[i]
return max_sum