20260228 144622 Cpp 入门第二十课

第二十章：动态规划——记住过去，规划未来 ¶

你好！欢迎来到第二十章！在前面的章节，我们学习了递推、递归、贪心等算法。这一章我们将学习一个更强大但也更有挑战的算法——动态规划。动态规划的核心思想是：把一个大问题拆分成许多小问题，并且记住这些小问题的答案，避免重复计算，从而高效地解决复杂问题。它就像我们做数学题时，记住已经算过的中间结果，直接拿来用，而不是每次都从头算起。

20.1 动态规划程序范例 ¶

先从一个最简单的例子开始：斐波那契数列。我们之前学过递归，但递归会重复计算很多次。比如算 fib(5) 时，fib(3) 被算了两次。动态规划就是用数组把算过的值存起来，避免重复。

#include <iostream>
using namespace std;

const int N = 100;
long long dp[N];  // dp[i] 存储第i个斐波那契数

long long fib(int n) {
    dp[1] = 1;
    dp[2] = 1;
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];  // 状态转移方程
    }
    return dp[n];
}

int main() {
    int n;
    cout << "请输入n：";
    cin >> n;
    cout << "第" << n << "项是：" << fib(n) << endl;
    return 0;
}

这个程序用数组记录了每个斐波那契数，从前往后依次计算，每个数只算一次，时间复杂度 O(n)，比递归的指数级快多了。这就是最简单的动态规划。

20.2 动态规划的用法 ¶

20.2.1 什么是动态规划？¶

动态规划（Dynamic Programming，简称DP）是一种通过把原问题分解为相对简单的子问题，并保存子问题的解来避免重复计算的方法。它通常用于求解具有最优子结构和重叠子问题性质的问题。

最优子结构：一个问题的最优解包含其子问题的最优解。比如，你要从北京到上海的最短路径，如果经过南京，那么北京到南京的路径也必须是北京到南京的最短路径。
重叠子问题：在求解过程中，相同的子问题会被多次用到。比如斐波那契数列，fib(3) 被多次用到。

20.2.2 动态规划的步骤 ¶

定义状态：用 dp 数组表示什么？比如 dp[i] 表示到达第 i 阶的方法数，或者 dp[i][j] 表示前 i 个物品在容量 j 下的最大价值。
确定状态转移方程：怎么从已知状态推出新状态？比如 dp[i] = dp[i-1] + dp[i-2]。
初始化：确定边界条件，比如 dp[1] = 1, dp[2] = 1。
计算顺序：通常是从小到大计算，保证计算当前状态时，所需子状态已经算好。
最终答案：从 dp 数组中取出所需结果。

20.2.3 动态规划的分类 ¶

线性DP：状态是一维的，如斐波那契、爬楼梯、最大子段和。
二维DP：状态是二维的，如背包问题、最长公共子序列。
区间DP：状态表示区间，如石子合并。
树形DP：在树上进行DP。

20.3 编程实例讲解 ¶

实例1：爬楼梯（线性DP）¶

题目：小明爬楼梯，每次可以跨1级或2级台阶。问爬到第n级台阶有多少种不同的爬法？

分析：
- 状态：dp[i] 表示爬到第 i 级的方法数。
- 转移：到第 i 级可以从 i-1 跨1步，或从 i-2 跨2步，所以 dp[i] = dp[i-1] + dp[i-2]。
- 初始化：dp[1] = 1, dp[2] = 2。

#include <iostream>
using namespace std;

int main() {
    int n;
    cout << "请输入台阶数：";
    cin >> n;
    if (n == 1) {
        cout << "1种" << endl;
        return 0;
    }
    int dp[100] = {0};
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    cout << "共有" << dp[n] << "种爬法" << endl;
    return 0;
}

实例2：最大子段和（线性DP）¶

题目：给定一个数组，求连续子数组的最大和。例如 [-2,1,-3,4,-1,2,1,-5,4] 的最大子段和是 4-1+2+1=6。

分析：
- 状态：dp[i] 表示以第 i 个元素结尾的最大子段和。
- 转移：要么自己单独开始一段（nums[i]），要么接在前一段后面（dp[i-1] + nums[i]），取较大值。即 dp[i] = max(nums[i], dp[i-1] + nums[i])。
- 最终答案：所有 dp[i] 中的最大值。

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    int dp[100];
    dp[0] = arr[0];
    int ans = dp[0];
    for (int i = 1; i < n; i++) {
        dp[i] = max(arr[i], dp[i-1] + arr[i]);
        ans = max(ans, dp[i]);
    }
    cout << "最大子段和：" << ans << endl;
    return 0;
}

实例3：01背包问题（二维DP）¶

题目：有 n 个物品，每个物品有重量 w[i] 和价值 v[i]。有一个容量为 C 的背包，问最多能装多少价值的物品？每个物品只能选或不选（0-1选择）。

分析：
- 状态：dp[i][j] 表示前 i 个物品中，选择总重量不超过 j 的最大价值。
- 转移：对于第 i 个物品，有两种选择：
- 不选：dp[i][j] = dp[i-1][j]
- 选（前提 j >= w[i]）：dp[i][j] = dp[i-1][j - w[i]] + v[i]
取最大值。
- 初始化：dp[0][j] = 0（没有物品时价值为0）。
- 最终答案：dp[n][C]。

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int n, C;
    cout << "请输入物品数量和背包容量：";
    cin >> n >> C;
    int w[100], v[100];
    for (int i = 1; i <= n; i++) {
        cin >> w[i] >> v[i];
    }

    int dp[100][100] = {0};  // dp[i][j] 表示前i个物品容量j的最大价值
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= C; j++) {
            dp[i][j] = dp[i-1][j];  // 不选第i个
            if (j >= w[i]) {
                dp[i][j] = max(dp[i][j], dp[i-1][j - w[i]] + v[i]);
            }
        }
    }
    cout << "最大价值：" << dp[n][C] << endl;
    return 0;
}

空间优化：可以用一维数组倒序更新，避免覆盖。

int dp[100] = {0};
for (int i = 1; i <= n; i++) {
    for (int j = C; j >= w[i]; j--) {
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }
}

实例4：最长上升子序列（LIS）¶

题目：给定一个序列，求最长严格上升子序列的长度（不要求连续）。例如 [10,9,2,5,3,7,101,18] 的最长上升子序列是 [2,5,7,101] 或 [2,3,7,101]，长度为4。

分析：
- 状态：dp[i] 表示以第 i 个元素结尾的最长上升子序列长度。
- 转移：对于每个 j < i，如果 a[j] < a[i]，则 dp[i] = max(dp[i], dp[j] + 1)。
- 初始化：dp[i] = 1（每个元素自己就是一个子序列）。
- 最终答案：所有 dp[i] 的最大值。

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int arr[] = {10, 9, 2, 5, 3, 7, 101, 18};
    int n = sizeof(arr) / sizeof(arr[0]);
    int dp[100];
    int ans = 1;
    for (int i = 0; i < n; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (arr[j] < arr[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        ans = max(ans, dp[i]);
    }
    cout << "最长上升子序列长度：" << ans << endl;
    return 0;
}

实例5：编辑距离（选做）¶

题目：给定两个字符串，允许插入、删除、替换字符，求将一个字符串变成另一个的最少操作次数。

分析：
- 状态：dp[i][j] 表示将 s1 的前 i 个字符变成 s2 的前 j 个字符的最少操作。
- 转移：
- 如果 s1[i-1] == s2[j-1]，则 dp[i][j] = dp[i-1][j-1]
- 否则，考虑三种操作：
- 插入：dp[i][j-1] + 1
- 删除：dp[i-1][j] + 1
- 替换：dp[i-1][j-1] + 1
取最小值。
- 初始化：dp[0][j] = j（插入j次），dp[i][0] = i（删除i次）。

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    string s1, s2;
    cout << "请输入两个字符串：" << endl;
    cin >> s1 >> s2;
    int m = s1.length(), n = s2.length();
    int dp[100][100];
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1[i-1] == s2[j-1]) {
                dp[i][j] = dp[i-1][j-1];
            } else {
                dp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + 1;
            }
        }
    }
    cout << "最少操作次数：" << dp[m][n] << endl;
    return 0;
}

20.4 阶段性编程练习 ¶

练习1：用动态规划求斐波那契数列的第50项（注意用 long long 或高精度）。
练习2：一个机器人从 (0,0) 走到 (m,n)，每次只能向右或向下，问有多少条路径？
练习3：给定一个数组，求最长连续递增子序列的长度（注意是连续）。
练习4：完全背包问题：每个物品可以选无限次，求最大价值。
练习5：数字三角形问题：输入一个数字三角形，求从顶部到底部的最大路径和（可以向下或右下）。