动态规划

1. 动态规划概述

• 动态规划(DP) : 是一种通过将复杂问题分解为更简单的子问题来解决问题的算法策略
• 核心思想：通过存储子问题的解来避免重复计算，从而提高算法效率
• 动态规划的两个关键特性：
  • 最优子结构：问题的最优解包含其子问题的最优解
  • 重叠子问题：同一个子问题在求解过程中会被多次使用

2. 区间DP基本概念

• 区间动态规划：是动态规划的一种特殊形式，用于解决在区间上进行操作的问题
• 核心思想：将区间问题分解为更小的区间子问题
• 状态定义：通常使用dp[i][j]表示区间[i,j]上的最优解
• 计算顺序：通常按照区间长度从小到大进行计算
• 适用问题：
  • 区间合并问题（如石子合并）
  • 区间分割问题（如矩阵链乘法）
  • 区间特性问题（如最长回文子序列）

3. 区间DP的特点

• 区间表示：使用两个下标i和j表示区间[i,j]
• 计算顺序：按照区间长度从小到大计算，确保子问题先于依赖它们的大问题求解
• 状态转移：通常涉及枚举区间内的分割点，将大区间问题分解为小区间问题
• 时间复杂度：通常为，其中是区间长度
  • 两层循环枚举区间起点和长度
  • 内层循环枚举分割点
• 空间复杂度：通常为，用于存储所有可能区间的结果

4. 区间DP的模板代码：基本模板

vector<vector<int>> dp(n, vector<int>(n, initial_value));// 初始化DP数组
// 初始化长度为1的区间（基础情况）
for (int i = 0; i < n; i++) {
    dp[i][i] = base_case_value;
}
// 按照区间长度递增计算
for (int len = 2; len <= n; len++) {
    // 枚举区间起点
    for (int i = 0; i <= n - len; i++) {
        int j = i + len - 1;  // 计算区间终点
        dp[i][j] = initial_extreme_value; // 初始化为最大/最小值       
        // 枚举分割点
        for (int k = i; k < j; k++) {
            dp[i][j] = min/max(dp[i][j], dp[i][k] + dp[k+1][j] + cost(i, j, k));// 状态转移
        }
    }
}
// 最终结果通常是dp[0][n-1]或dp[1][n]
return dp[0][n-1];

4. 区间DP的模板代码：记忆化搜索实现区间DP

vector<vector<int>> memo(n, vector<int>(n, -1));// 初始化记忆化数组
// 递归函数
int solve(int i, int j) {
    // 基础情况
    if (i == j) return base_case_value;
    // 如果已经计算过，直接返回结果
    if (memo[i][j] != -1) return memo[i][j];
    int result = initial_extreme_value;// 初始化为最大/最小值
    // 枚举分割点
    for (int k = i; k < j; k++) {
        result = min/max(result, solve(i, k) + solve(k+1, j) + cost(i, j, k)); // 状态转移
    }
    // 存储结果
    memo[i][j] = result;
    return result;
}
return solve(0, n-1);// 调用入口

5.1 实例分析：石子合并

问题描述：
有N堆石子排成一排，每堆石子有一定的质量。现在要将这N堆石子合并成一堆，每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和。问题是：将N堆石子合并成一堆，最小的总代价是多少？

分析：

• 状态定义：dp[i][j]表示将区间[i,j]内的石子合并成一堆的最小代价
• 状态转移：枚举区间内的分割点k，dp[i][j] = min(dp[i][k] + dp[k+1][j] + sum(i,j))
• 其中sum(i,j)是区间[i,j]内所有石子的质量之和
• 初始条件：dp[i][i] = 0（单堆石子不需要合并）

5.2 实例分析：最长回文子序列

问题描述：
给定一个字符串s，找出其中最长的回文子序列，并返回该序列的长度。子序列是指从原序列中可以通过删除某些字符（也可以不删除）而不改变剩余字符相对位置形成的新序列。

分析：

• 状态定义：dp[i][j]表示字符串s在区间[i,j]上的最长回文子序列长度
• 状态转移：
  • 如果s[i] == s[j]，则dp[i][j] = dp[i+1][j-1] + 2
  • 否则，dp[i][j] = max(dp[i+1][j], dp[i][j-1])
• 初始条件：dp[i][i] = 1（单个字符是长度为1的回文）

5.3 实例分析：矩阵链乘法

问题描述：
给定n个矩阵的链，矩阵i的维度为p[i-1] x p[i]。求完成所有矩阵相乘所需的最小标量乘法次数。

分析：

• 状态定义：dp[i][j]表示计算矩阵链A[i]A[i+1]...A[j]所需的最小乘法次数
• 状态转移：枚举分割点k，dp[i][j] = min(dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j])
• 其中p[i-1]*p[k]*p[j]是合并两个子矩阵链的代价
• 初始条件：dp[i][i] = 0（单个矩阵不需要乘法）