C++动态规划教程：从0基础开始

动态规划（Dynamic Programming，简称DP）是一种通过将复杂问题分解为重叠子问题，并存储子问题的解来避免重复计算的算法思想。本教程将从基础概念开始，通过具体示例带你逐步掌握动态规划的核心思想和实现方法。

什么是动态规划？

动态规划适合解决具有以下特点的问题：

1. 存在重叠子问题 - 问题可以分解为重复出现的子问题
2. 具有最优子结构 - 问题的最优解包含子问题的最优解
3. 可以定义状态转移方程 - 用数学公式描述问题与子问题的关系

第一个动态规划问题：斐波那契数列

斐波那契数列是理解动态规划的绝佳例子，数列定义为：

• F(0) = 0
• F(1) = 1
• F(n) = F(n-1) + F(n-2)（n ≥ 2）

递归解法（存在问题）

首先看一个直观但效率低下的递归解法：

#include <iostream>
using namespace std;

// 递归计算斐波那契数
int fib(int n) {
    // 基本情况
    if (n <= 1) {
        return n;
    }
    // 递归调用
    return fib(n-1) + fib(n-2);
}

int main() {
    int n = 10;
    cout << "斐波那契数 F(" << n << ") = " << fib(n) << endl;
    return 0;
}

问题分析：这个解法存在大量重复计算，例如计算F(5)时需要计算F(4)和F(3)，而计算F(4)时又需要计算F(3)，导致时间复杂度为O(2ⁿ)。

动态规划解法1：备忘录法（自顶向下）

备忘录法通过存储已经计算过的结果来避免重复计算：

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

// 备忘录数组，用于存储已经计算过的结果
vector<int> memo;

// 带备忘录的递归函数
int fib(int n) {
    // 基本情况
    if (n <= 1) {
        return n;
    }
    
    // 如果已经计算过，直接返回备忘录中的结果
    if (memo[n] != -1) {
        return memo[n];
    }
    
    // 否则计算并存储结果到备忘录
    memo[n] = fib(n-1) + fib(n-2);
    return memo[n];
}

int main() {
    int n = 10;
    // 初始化备忘录，大小为n+1，初始值为-1表示未计算
    memo.resize(n+1, -1);
    
    cout << "斐波那契数 F(" << n << ") = " << fib(n) << endl;
    return 0;
}

优化分析：备忘录法将时间复杂度降至O(n)，空间复杂度为O(n)。

动态规划解法2：迭代法（自底向上）

迭代法从最小的子问题开始计算，逐步构建出更大问题的解：

#include <iostream>
using namespace std;

// 迭代法计算斐波那契数
int fib(int n) {
    // 基本情况
    if (n <= 1) {
        return n;
    }
    
    // 定义前两个数
    int prev_prev = 0;  // F(0)
    int prev = 1;       // F(1)
    int current;        // 用于存储当前计算的数
    
    // 从F(2)计算到F(n)
    for (int i = 2; i <= n; i++) {
        current = prev + prev_prev;  // F(i) = F(i-1) + F(i-2)
        prev_prev = prev;            // 更新前两个数
        prev = current;
    }
    
    return current;
}

int main() {
    int n = 10;
    cout << "斐波那契数 F(" << n << ") = " << fib(n) << endl;
    return 0;
}

优化分析：迭代法同样将时间复杂度降至O(n)，但空间复杂度优化到了O(1)，因为我们只需要存储前两个数。

经典动态规划问题：爬楼梯

问题描述：有n级台阶，每次可以爬1级或2级台阶，问有多少种不同的方法可以爬到楼顶？

分析：

• 爬上第n级台阶的方法数 = 爬上第n-1级台阶的方法数 + 爬上第n-2级台阶的方法数
• 基本情况：F(1) = 1，F(2) = 2

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

// 方法1：使用DP数组
int climbStairs1(int n) {
    // 处理特殊情况
    if (n <= 2) {
        return n;
    }
    
    // 创建DP数组，dp[i]表示爬上i级台阶的方法数
    vector<int> dp(n + 1);
    
    // 初始化基本情况
    dp[1] = 1;
    dp[2] = 2;
    
    // 填充DP数组
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    
    return dp[n];
}

// 方法2：优化空间，只存储前两个值
int climbStairs2(int n) {
    // 处理特殊情况
    if (n <= 2) {
        return n;
    }
    
    // 只保留前两个值，节省空间
    int prev_prev = 1;  // 对应dp[i-2]
    int prev = 2;       // 对应dp[i-1]
    int current;        // 对应dp[i]
    
    // 计算从3到n的情况
    for (int i = 3; i <= n; i++) {
        current = prev + prev_prev;
        prev_prev = prev;
        prev = current;
    }
    
    return current;
}

int main() {
    int n = 5;
    cout << "爬上" << n << "级台阶的方法数（方法1）：" << climbStairs1(n) << endl;
    cout << "爬上" << n << "级台阶的方法数（方法2）：" << climbStairs2(n) << endl;
    return 0;
}

动态规划解题步骤总结

通过以上例子，我们可以总结出动态规划的一般解题步骤：

1. 定义状态：明确dp[i]（或多维dp[i][j]）代表什么
2. 确定状态转移方程：找出dp[i]与dp[i-1]等之前状态的关系
3. 初始化基本情况：设置最小子问题的解
4. 确定计算顺序：自底向上或自顶向下
5. 计算并返回结果

进阶问题：最大子数组和

问题描述：给定一个整数数组nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

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

int maxSubArray(vector<int>& nums) {
    // 处理空数组情况
    if (nums.empty()) {
        return 0;
    }
    
    int n = nums.size();
    // dp[i]表示以nums[i]结尾的最大子数组和
    vector<int> dp(n);
    
    // 初始化：第一个元素的最大子数组和就是它本身
    dp[0] = nums[0];
    // 记录全局最大值
    int max_sum = dp[0];
    
    // 填充DP数组
    for (int i = 1; i < n; i++) {
        // 状态转移方程：
        // 要么将当前元素加入之前的子数组，要么从当前元素重新开始一个子数组
        dp[i] = max(nums[i], dp[i-1] + nums[i]);
        // 更新全局最大值
        max_sum = max(max_sum, dp[i]);
    }
    
    return max_sum;
}

// 优化空间复杂度的版本
int maxSubArrayOptimized(vector<int>& nums) {
    if (nums.empty()) {
        return 0;
    }
    
    int n = nums.size();
    int current_max = nums[0];  // 代替dp[i]
    int max_sum = nums[0];      // 全局最大值
    
    for (int i = 1; i < n; i++) {
        current_max = max(nums[i], current_max + nums[i]);
        max_sum = max(max_sum, current_max);
    }
    
    return max_sum;
}

int main() {
    vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    cout << "最大子数组和（标准DP）：" << maxSubArray(nums) << endl;
    cout << "最大子数组和（优化空间）：" << maxSubArrayOptimized(nums) << endl;
    return 0;
}

二维动态规划：最长公共子序列

问题描述：给定两个字符串text1和text2，返回它们最长公共子序列的长度。子序列是指通过删除一些字符而不改变其余字符顺序的情况下得到的序列。

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

int longestCommonSubsequence(string text1, string text2) {
    int m = text1.length();
    int n = text2.length();
    
    // 创建二维DP数组，dp[i][j]表示text1[0..i-1]和text2[0..j-1]的最长公共子序列长度
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    
    // 填充DP数组
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            // 如果当前字符相同，则当前长度 = 前一个长度 + 1
            if (text1[i - 1] == text2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                // 如果当前字符不同，则取左边或上边的最大值
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    
    // 返回最终结果
    return dp[m][n];
}

int main() {
    string text1 = "abcde";
    string text2 = "ace";
    
    cout << "最长公共子序列长度：" << longestCommonSubsequence(text1, text2) << endl;
    return 0;
}

总结

动态规划是一种强大的算法设计思想，通过将复杂问题分解为重叠子问题并存储中间结果，能够显著提高算法效率。本教程介绍了动态规划的基本概念和几个经典问题的解法，包括：

1. 斐波那契数列 - 展示了从递归到动态规划的优化过程
2. 爬楼梯问题 - 进一步巩固动态规划思想
3. 最大子数组和 - 展示了一维动态规划的应用
4. 最长公共子序列 - 介绍了二维动态规划的应用

要掌握动态规划，关键在于多练习，学会分析问题的状态和状态转移方程。随着练习的深入，你会逐渐培养出对动态规划问题的直觉，能够快速识别适合用动态规划解决的问题并设计出高效的算法。