一维动态规划

一维动态规划：从楼梯问题到生活中的“递推”思维

你有没有想过，上楼梯的时候，如果一次可以跨1级或2级，那从地面走到第10级台阶一共有多少种走法？这个问题看起来有点绕，但用动态规划（DP）就能轻松搞定。一维动态规划是动态规划中最简单、最基础的形式——它用一个一维数组（比如 dp[0..n]）来保存从开始到每个位置的最优答案。很多线性递推问题（比如爬楼梯、零花钱存钱方案、考试得分统计）都可以用这种方法解决。

什么是一维动态规划？

简单说，就是用数组把问题拆成一串小问题，每个小问题的答案只依赖前面几个小问题的答案。就像玩多米诺骨牌，推倒第一张，后面的就会依次倒下。这个“数组”就是 dp（dynamic programming的缩写），它记录每个“状态”（比如走到第几级台阶、存到第几天）的结果。

一维DP有三个关键要素：

1. 状态：dp[i] 表示什么？比如 dp[i] 表示走到第 i 级台阶的方法数。
2. 状态转移方程：dp[i] 怎么从更小的状态算出来？比如 dp[i] = dp[i-1] + dp[i-2]。
3. 边界条件：最开始的几个值怎么定？比如 dp[1] = 1, dp[2] = 2。

掌握了这三个，一维DP就基本拿下了。

经典例子：上楼梯问题（一步一步推）

假设楼梯有 n 级，每次可以走1级或2级，问有多少种不同的走法。
生活联想：就像你每天上学，可以坐一趟公交车（1步）或者骑自行车（2步），但你想知道从家到学校有多少种不同的交通组合方式（当然，这里步数只代表一次动作，实际可以混合）。

分析：

• 走到第 i 级台阶，最后一步可能是从第 i-1 级跨1级上来的，也可能是从第 i-2 级跨2级上来的。
• 所以走到第 i 级的方法数 = 走到第 i-1 级的方法数 + 走到第 i-2 级的方法数。
• 这就是状态转移方程：dp[i] = dp[i-1] + dp[i-2]。

边界条件（最小的台阶）：

• 走到第1级：只能一次跨1级，所以只有1种方法。
• 走到第2级：可以两次1级，或者一次2级，共2种方法。
• 注意：第0级（地面）？有的写法会把 dp[0] 设为1（表示站在地面也是一种状态），但初学者可以直接从1和2开始。

代码实现：

#include <iostream>
using namespace std;

int main() {
    int n = 5; // 楼梯级数，可以改成10或20
    int dp[100] = {0}; // dp[i]表示走到第i级台阶的方法数，数组长度要足够大
    
    // 边界条件
    dp[1] = 1; // 走到第1级：1种方法
    dp[2] = 2; // 走到第2级：2种方法（1+1 或 2）
    
    // 从第3级开始递推
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2]; // 状态转移方程
    }
    
    cout << "上" << n << "级台阶共有" << dp[n] << "种方法" << endl;
    return 0;
}

运行结果：上5级台阶共有8种方法（你可以自己验证：一级一级数一数？1,2,3,5,8……其实就是斐波那契数列！）。

生活中更多例子：零花钱存钱方案

假设你每天有5元零花钱，但你想攒钱买一个50元的玩具。你每天可以存5元，或者不存（花掉）。如果你连续存了3天，第4天可以选择继续存或不存，但第4天的存款总额等于前一天的总额加5（如果存）或者不变（如果不存）。这其实就是一个一维DP问题，不过这里“状态”变成了“第 i 天结束时你存了多少钱”？

其实更简单的例子是：考试得分累加。你参加了5次测验，每次的得分分别是80,90,70,85,95，你想知道从第1次到第i次的总分。那 dp[i] = dp[i-1] + score[i]，这就是一维DP的另一种形式（累加型）。而“上楼梯”是“累加型”的变种，只是系数变成了之前的和。

新手容易犯的错误

1. 数组下标越界：比如 int dp[100]，却访问 dp[100]（下标最大99）。一般建议数组开大一点，比如 dp[1005]，或者根据 n 动态分配。
2. 忘记边界条件：如果只写 dp[1]=1 而不写 dp[2]=2，那么计算 dp[3] 时 dp[2] 是0，结果会错。
3. 把递推方向搞反：比如从大到小循环 for (int i=n; i>=3; i--)，那就错了，因为计算 dp[i] 时需要 dp[i-1] 和 dp[i-2]，而它们还没被算出来。必须从小到大。
4. 误解状态含义：比如把 dp[i] 理解成“走到第i级的方法数”，但混淆了“步数”和“方法数”——有时候初学者会误以为走1步和2步是不同“方法”的计数，其实这里方法数就是组合数。

完整代码示例（带输入输出和异常处理）

下面是一个可以自行输入楼梯级数的完整程序，并包含对 n=1 和 n=0 的特殊处理（n=0时表示地面，方法数通常认为是1，但实际情况中很少出现）。

#include <iostream>
using namespace std;

int main() {
    int n; // 楼梯级数
    cout << "请输入楼梯的级数（正整数）：";
    cin >> n;
    
    if (n <= 0) {
        cout << "输入无效，请重新输入正整数。" << endl;
        return 1;
    }
    
    // 数组大小设为 n+2 防止越界
    int dp[n+2] = {0}; // dp[i]表示走到第i级的方法数
    
    // 边界条件
    dp[1] = 1; // 只有一级：1种
    if (n >= 2) {
        dp[2] = 2; // 两级：2种
    }
    
    // 递推计算
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    
    cout << "上" << n << "级台阶共有" << dp[n] << "种方法。" << endl;
    return 0;
}

测试一下：
输入 1 → 输出 1
输入 2 → 输出 2
输入 3 → 输出 3（1+1+1, 1+2, 2+1）
输入 10 → 输出 89（增长很快！）

更多应用：“最大连续子段和”也是一维DP

除了计数问题，一维DP还可以求“最优值”。比如给你一个数组，找出连续的一段（子段），使得这段数字的和最大。比如考试得分：[ -2, 1, -3, 4, -1, 2, 1, -5, 4 ]，最大连续子段和是多少？答案是6（子段为[4,-1,2,1]）。这个问题可以用一维DP解决：dp[i] 表示以第 i 个元素结尾的最大子段和，转移方程是 dp[i] = max( a[i], dp[i-1] + a[i] )。这里 dp[i] 只依赖前一个状态，也是一维DP的典型应用。你学会了上楼梯，就能轻松理解这个啦！

相关指引

如果你想继续探索动态规划，可以看看：

• 二维动态规划：比如走格子（从左上角到右下角有多少条路径），需要 dp[i][j] 两个维度。
• 背包问题：比如你有20元，能买几种零食，每种零食有价格和美味值，怎么组合最美味？这是更复杂的DP，但思想一样：把大问题拆成小问题。
• 记忆化搜索：递归+备忘录，和DP本质相同，但写法不同。

一维DP是动态规划的“敲门砖”，多练几个题，比如“斐波那契数列”、“爬楼梯”、“最大子段和”，你会发现“递推”思维无处不在，就连每天存零花钱、规划作业时间都可以用上它！