区间 DP：戳气球、石子合并

区间 DP 思路

区间 DP 的核心：枚举区间长度 → 枚举区间左端点 → 枚举分割点。

// 通用模板
for (int len = 2; len <= n; len++) {      // 枚举区间长度
    for (int i = 0; i + len - 1 < n; i++) { // 枚举左端点
        int j = i + len - 1;               // 右端点
        for (int k = i; k < j; k++) {      // 枚举分割点
            dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k+1][j] + cost);
        }
    }
}

最长回文子序列（LeetCode 516）

dp[i][j] = s[i..j] 内最长回文子序列的长度：

public int longestPalindromeSubseq(String s) {
    int n = s.length();
    int[][] dp = new int[n][n];
    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.charAt(i) == s.charAt(j)) dp[i][j] = dp[i+1][j-1] + 2;
            else dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
        }
    }
    return dp[0][n-1];
}

戳气球（LeetCode 312）

dp[i][j] = 戳破 (i,j) 区间内所有气球获得的最大硬币数（i、j 是边界不戳）：

关键：枚举最后戳破的气球 k（保证 i 和 j 仍在）：

public int maxCoins(int[] nums) {
    int n = nums.length;
    int[] arr = new int[n+2];
    arr[0] = arr[n+1] = 1;
    for (int i = 0; i < n; i++) arr[i+1] = nums[i];
    int N = n + 2;
    int[][] dp = new int[N][N];
    for (int len = 2; len < N; len++) {
        for (int i = 0; i + len - 1 < N; i++) {
            int j = i + len - 1;
            for (int k = i+1; k < j; k++) {
                dp[i][j] = Math.max(dp[i][j],
                    dp[i][k] + arr[i]*arr[k]*arr[j] + dp[k][j]);
            }
        }
    }
    return dp[0][N-1];
}

石子合并（区间DP经典）

把 n 堆石子合并成 1 堆，每次相邻两堆合并，代价是合并后总数，求最小代价：

public int stoneGame(int[] stones) {
    int n = stones.length;
    int[] prefix = new int[n+1];
    for (int i = 0; i < n; i++) prefix[i+1] = prefix[i] + stones[i];
    int[][] dp = new int[n][n];
    // 长度1的区间代价为0
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;
            dp[i][j] = Integer.MAX_VALUE;
            for (int k = i; k < j; k++) {
                int cost = prefix[j+1] - prefix[i]; // 合并 [i..j] 的代价
                dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k+1][j] + cost);
            }
        }
    }
    return dp[0][n-1];
}

总结