一、算法概述

区间动态规划（Interval DP）是动态规划中处理区间问题的一类方法。它的核心特征是以区间作为状态，大区间的解由若干小区间的解合并得到。

典型问题包括：

  • 石子合并问题： 将多堆石子合并成一堆，每次合并相邻两堆，求最小/最大代价
  • 矩阵链相乘： 求矩阵相乘的最优加括号方式
  • 最长回文子序列： 求序列中最长的回文子序列
  • 戳气球： LeetCode 312

二、核心思想

区间 DP 的基本模型：

  • 状态定义： dp[i][j] 表示区间 [i, j] 上的最优解
  • 状态转移： 枚举区间内的分割点 k，将 [i, j] 分成 [i, k] 和 [k+1, j]，合并子区间的解

标准三重循环框架：

for len = 2 to n:              // 枚举区间长度（从小到大）
    for i = 0 to n-len:        // 枚举区间起点
        j = i + len - 1        // 计算区间终点
        for k = i to j-1:      // 枚举分割点
            dp[i][j] = merge(dp[i][k], dp[k+1][j])

核心要点： 必须按区间长度从小到大递推，确保在处理大区间时所有小区间已经计算完毕。

三、算法步骤 / 伪代码

输入: 数组 a[0..n-1]（石子重量等）
输出: 最优代价

初始化 dp[i][i] = base_case  （区间长度为 1 的初始状态）

for len = 2 to n:                     // 区间长度
    for i = 0 to n-len:               // 起点
        j = i + len - 1               // 终点
        for k = i to j-1:             // 分割点
            dp[i][j] = better( dp[i][j], combine(dp[i][k], dp[k+1][j]) )

返回 dp[0][n-1]

四、C++ 代码实现

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

// ==================== 问题1：石子合并 ====================
// 有 n 堆石子排成一行，每次合并相邻两堆，代价为两堆石子数之和
// 求将所有石子合并成一堆的最小代价（也可求最大代价）

void stoneMerge() {
    cout << "====== 石子合并问题 ======" << endl;
    cout << "请输入石子堆数: ";
    int n;
    cin >> n;

    vector<int> stones(n);
    cout << "请输入每堆石子数: ";
    for (int i = 0; i < n; i++) cin >> stones[i];

    // 前缀和，用于 O(1) 计算区间石子总数
    vector<int> prefix(n + 1, 0);
    for (int i = 0; i < n; i++)
        prefix[i + 1] = prefix[i] + stones[i];

    // dp[i][j] = 合并区间 [i, j] 的最小代价
    vector<vector<int>> dp(n, vector<int>(n, INT_MAX));

    // 初始化：单堆石子不需要合并，代价为 0
    for (int i = 0; i < n; i++)
        dp[i][i] = 0;

    // 按区间长度递推
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;
            int sum = prefix[j + 1] - prefix[i];  // 区间 [i, j] 的石子总数

            for (int k = i; k < j; k++) {
                // 合并 [i,k] 和 [k+1,j]，代价 = 子区间代价 + 本区间石子总数
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + sum);
            }
        }
    }

    cout << "合并所有石子的最小代价: " << dp[0][n - 1] << endl;
}

// ==================== 问题2：最长回文子序列 ====================
// 求字符串中最长回文子序列的长度（LeetCode 516）
// dp[i][j] = s[i..j] 中最长回文子序列的长度

int longestPalindromeSubseq(const string& s) {
    int n = s.length();
    vector<vector<int>> dp(n, vector<int>(n, 0));

    // 初始化：单个字符的回文子序列长度为 1
    for (int i = 0; i < n; i++)
        dp[i][i] = 1;

    for (int len = 2; len <= n; len++) {
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;

            if (s[i] == s[j]) {
                // 两端字符相等，内部回文 + 2
                dp[i][j] = dp[i + 1][j - 1] + 2;
            } else {
                // 两端字符不等，取去掉一端后的最大值
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }

    return dp[0][n - 1];
}

int main() {
    // ---- 石子合并 ----
    stoneMerge();

    // ---- 最长回文子序列 ----
    cout << "\n====== 最长回文子序列 ======" << endl;
    cout << "请输入一个字符串: ";
    string s;
    cin >> s;
    int lps = longestPalindromeSubseq(s);
    cout << "最长回文子序列长度: " << lps << endl;

    return 0;
}

五、复杂度分析

指标 复杂度 说明
时间复杂度 O(n³) 三重循环：区间长度 × 起点 × 分割点
空间复杂度 O(n²) dp 表大小为 n×n

优化技巧：

  • 使用前缀和（石子合并）可在 O(1) 时间内获得区间和
  • 部分区间 DP 问题存在 O(n²) 或 O(n log n) 的四边形不等式优化，但理解难度较大

六、应用场景

  1. 石子合并问题： 经典区间 DP 入门题
  2. 矩阵链相乘： A1 × A2 × ... × An，求最少乘法次数
  3. 回文相关问题： 最长回文子序列、回文子串计数
  4. 戳气球 (Burst Balloons)： LeetCode 312
  5. 多边形三角剖分： 求最优剖分的最小代价
  6. 表达式求值： 加括号使得表达式结果最大/最小
  7. 字符串折叠 / 编码压缩： 用区间 DP 求最优压缩

七、经典例题

例题一：石子合并（最小代价）

题目描述： 有 N 堆石子排成一排，第 i 堆有 a[i] 个石子。每次合并相邻两堆，合并代价为两堆石子数之和。求合并成一堆的最小总代价。

题解见上方代码 stoneMerge() 函数。

例题二：LeetCode 516. 最长回文子序列

题目描述： 给定一个字符串 s，找出其中最长的回文子序列，并返回该序列的长度。

题解见上方代码 longestPalindromeSubseq() 函数，完整提交版如下：

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n = s.length();
        vector<vector<int>> dp(n, vector<int>(n, 0));

        for (int i = 0; i < n; i++)
            dp[i][i] = 1;

        for (int len = 2; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                if (s[i] == s[j])
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                else
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
            }
        }

        return dp[0][n - 1];
    }
};

例题三：LeetCode 312. 戳气球

题目描述： 有 n 个气球，每个气球上有一个数字 nums[i]。戳破气球 i 可以得到 nums[i-1] * nums[i] * nums[i+1] 枚硬币。求最多能获得的硬币数。

区间 DP 解法：

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        int n = nums.size();
        // 两端补 1
        vector<int> val(n + 2, 1);
        for (int i = 0; i < n; i++) val[i + 1] = nums[i];

        vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));

        for (int len = 1; len <= n; len++) {
            for (int i = 1; i + len - 1 <= n; i++) {
                int j = i + len - 1;
                // k 是区间 [i, j] 中最后一个被戳破的气球
                for (int k = i; k <= j; k++) {
                    int coins = dp[i][k - 1] + dp[k + 1][j] 
                              + val[i - 1] * val[k] * val[j + 1];
                    dp[i][j] = max(dp[i][j], coins);
                }
            }
        }
        return dp[1][n];
    }
};
  1. Language
  2. 兼容模式
  3. 主题
  3. Worker 0, 18ms
  4. Powered by Hydro v5.0.1 Community