一维动态规划
困难13一维动态规划：用一根绳子串起所有答案
什么是动态规划？为什么只需要一维？
想象你在玩一个闯关游戏，每一关都有一个分数（可以是正数也可以是负数）。你只能往前走，而且每次只能从当前关的前面一两关跳过来。你想拿到从起点到终点的最高总分。这种“每走一步都依赖于前面少数几步”的问题，就能用一维动态规划轻松解决。
一维动态规划就像一个数组 dp[i]，它记录着“走到第 i 个位置时能得到的最佳结果”。我们只需要根据前面的 dp 值（比如 dp[i-1]、dp[i-2]），结合当前步骤的代价或收益，就能算出新的 dp[i]。整个过程就像串珠子——每个珠子只跟它前面几个珠子连着，顺着绳子一颗一颗穿下去就行了。
生活中的情景：糖果收集任务
小明参加了一个游戏：一条路上有 N 个格子，每个格子里放着一颗糖果，糖果数可能不同。小明从第 1 格出发，每次可以向前走一步（到下一格）或者向前走两步（跳过一格）。他不能后退，每个格子只能踩一次。他想收集到最多的糖果，问他最多能拿到多少颗？
我们可以用一维数组 dp[i] 表示“走到第 i 个格子上，最多能拿到的糖果总数”。那么：
- 要到达第 i 格，小明可能从第
i-1格跳过来，也可能从第i-2格跳过来。 - 所以走到第 i 格的最大糖果数，等于“前面能到达第 i 格的那一格的最大值”加上本格糖果数。
状态转移方程：
dp[i] = max(dp[i-1], dp[i-2]) + candy[i]
其中 candy[i] 是第 i 格的糖果数。边界条件：dp[1] = candy[1]；dp[2] = candy[1] + candy[2]（因为只能从第 1 格走一步过来，没有别的选择）。
最后答案就是 dp[N]。
这个例子展示了动态规划的三个核心要素：
- 状态定义：
dp[i]表示什么。 - 转移方程：怎么从以前的状态推出当前状态。
- 边界条件：最前面几个格子怎么处理。
经典问题：最大子段和（完整详解）
这是最常用来入门一维动态规划的题目。题目：给你一个整数数组 a[1..n]，请你找出一个连续的子数组（子段），使得它的和最大。例如，a = [ -2, 1, -3, 4, -1, 2, 1, -5, 4 ]，最大子段和是 4 + (-1) + 2 + 1 = 6。
1. 状态定义
定义 dp[i] 表示“以第 i 个元素结尾的连续子数组的最大和”。注意，这个子数组必须包含 a[i]。
2. 状态转移
对于 a[i]，有两种情况：
- 它自己一个人组成一个子数组：
a[i] - 它和前面以
a[i-1]结尾的最大子数组接在一起：dp[i-1] + a[i]
我们取两者中较大的那个：
dp[i] = max(a[i], dp[i-1] + a[i])
3. 边界条件
从 i = 1 开始，dp[1] = a[1]。
4. 最终答案
答案是所有 dp[i] 中的最大值，因为最大子段和一定是以某个元素结尾的。
5. 完整代码（带详细注释）
#include <iostream>
#include <algorithm> // 使用 max 函数
using namespace std;
int main() {
int n;
cin >> n;
int a[1005]; // 存储原始数组
for (int i = 1; i <= n; i++) {
cin >> a[i]; // 读入每个元素
}
int dp[1005]; // dp[i]表示以第i个元素结尾的最大子段和
dp[1] = a[1]; // 边界：第一个元素自己就是一个子段
int ans = dp[1]; // 答案初始化为第一个元素
for (int i = 2; i <= n; i++) {
// 转移：要么自己开始新子段，要么接上前面的子段
dp[i] = max(a[i], dp[i-1] + a[i]);
// 更新全局最大值
if (dp[i] > ans) {
ans = dp[i];
}
}
cout << ans << endl; // 输出最大子段和
return 0;
}
6. 手动模拟帮助理解
以数组 [ -2, 1, -3, 4, -1, 2, 1, -5, 4 ] 为例：
| i | a[i] | dp[i] 计算过程 | dp[i] | 当前最大值(ans) |
|---|---|---|---|---|
| 1 | -2 | 边界 | -2 | -2 |
| 2 | 1 | max(1, -2+1)=max(1,-1)=1 | 1 | 1 |
| 3 | -3 | max(-3, 1+(-3)) = max(-3,-2) = -2 | -2 | 1 |
| 4 | 4 | max(4, -2+4)=max(4,2)=4 | 4 | 4 |
| 5 | -1 | max(-1, 4+(-1))=max(-1,3)=3 | 3 | 4 |
| 6 | 2 | max(2, 3+2)=max(2,5)=5 | 5 | 5 |
| 7 | 1 | max(1, 5+1)=max(1,6)=6 | 6 | 6 |
| 8 | -5 | max(-5, 6+(-5))=max(-5,1)=1 | 1 | 6 |
| 9 | 4 | max(4, 1+4)=max(4,5)=5 | 5 | 6 |
最终答案 6 对应子段 [4, -1, 2, 1]。
新手常犯的错误
❌ 错误1：搞错状态含义
有人会把 dp[i] 定义为“前 i 个元素的最大子段和”（而不是以 i 结尾），这样会导致转移困难，因为子段不一定要包含第 i 个元素。
正确做法：严格按照“以 i 结尾”来定义，这样才能利用连续性。
❌ 错误2：忘记边界条件
如果不给 dp[1] 赋值就直接进入循环，dp[0] 未定义，会得到随机值。或者对于长度只有1的数组，循环体不执行，答案可能取不到。
正确做法：先处理边界，再写循环。
❌ 错误3：数组索引越界
代码中数组长度声明为 1005，但输入的 n 可能大于这个数（如果题目没有约束）。或者循环中错误地使用了 i-2 却没有处理 i=1 的情况。
正确做法：根据题目范围开足够大的数组，或者用 vector 动态分配。
❌ 错误4：漏掉所有负数的情况
当数组全部为负数时，最大子段和应该是最大的那个负数（因为不能选空子段）。上面的转移 max(a[i], dp[i-1]+a[i]) 能正确处理，因为 dp[i-1] 会逐渐变小，最终 dp[i] 会取到 a[i] 本身。但有些初学者会误以为答案为0（空子段），这要看题目要求。一般题目要求非空子段，所以答案不会是0。
扩展：另一个常见例子——爬楼梯（零花钱版）
小华每天放学后需要爬一段楼梯才能到家。楼梯有 N 级台阶，每级台阶上放了几毛钱零花钱（有正数也有负数，表示要交罚款）。他每次可以跨 1 级或 2 级台阶，并且要收集经过的台阶上的零花钱。问他到家时最多能拿到多少钱？
这跟前面的糖果收集完全一样，只是换了个名字。状态转移：dp[i] = max(dp[i-1], dp[i-2]) + money[i]，边界：dp[1]=money[1], dp[2]=money[1]+money[2]（或者也可以直接从地面起步，需要定义 dp[0]=0）。这就是一维动态规划在最短路/最优路径问题中的典型应用。
相关指引
掌握了“一维DP”的思想后，你可以挑战更复杂的问题：
- 背包问题：需要两维（物品和容量），但本质还是“每一步只依赖前面少数状态”。
- 最长上升子序列：可以用一维DP解决，但转移需要扫描前面所有 j<i，复杂度 O(n²)；可以进一步优化到 O(n log n)（贪心+二分）。
- 区间动态规划：比如合并石子，状态变成二维
dp[l][r]，表示区间内的最优解。 - 记忆化搜索：是DP的递归实现方式，适合状态转移图比较复杂的题目。
动态规划的核心是**“无后效性”和“最优子结构”**，一维DP是最简单的实践场。先从这类问题开始，把状态、转移、边界练熟，后面再学习更高维的DP就会容易很多。
小练习（可以自己试试看）
假设你每天有零花钱 a[i]，你可以选择连续几天不花（存起来），但是一旦开始花，就必须连续花下去直到结束。你希望找出一段连续的日子，使得净赚最多（收入减去支出）。这不就是最大子段和吗？现在把题目变一下：你不能选空区间，并且你可以在任意时间暂停一次（即可以断开一次），此时最大收益是多少？（提示：需要两个状态数组，一个表示还没暂停，一个表示已经暂停了。）
例题精讲
在求解斐波那契数列第n项（F(1)=1, F(2)=1, F(n)=F(n-1)+F(n-2)）时，若使用一维动态规划，以下哪个状态转移方程是正确的？（n≥3）
爬楼梯问题：每次可以爬1阶或2阶，求爬到第n阶有多少种不同的方法。若用一维DP，dp[0]=1, dp[1]=1。以下初始化正确的是？
对于一维动态规划问题，如果状态的转移只依赖于前一个状态，则可以使用滚动数组优化空间复杂度到O(1)。
给定一个整数数组nums，求不相邻元素的最大和（打家劫舍问题）。以下是一维动态规划实现，请补全代码。
int rob(vector<int>& nums) {
int n = nums.size();
if (n == 0) return 0;
if (n == 1) return nums[0];
vector<int> dp(n);
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
for (int i = 2; i < n; i++) {
dp[i] = max(dp[i-1], ___);
}
return dp[n-1];
}最长递增子序列（LIS）问题：给定数组arr，求最长严格递增子序列的长度。以下是一维DP实现，请补全代码。
int LIS(vector<int>& arr) {
int n = arr.size();
if (n == 0) return 0;
vector<int> dp(n, 1);
int ans = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (arr[j] < arr[i]) {
dp[i] = max(dp[i], ___);
}
}
ans = max(ans, dp[i]);
}
return ans;
}