区间动态规划为何要按长度递增遍历从矩阵链乘法到戳气球的完整LeetCode通关指南

// 正确的遍历顺序：按区间长度递增
for (int len = 1; len <= n; len++) {          // 区间长度
    for (int l = 0; l + len - 1 < n; l++) {   // 左端点
        int r = l + len - 1;                   // 右端点
        // 状态转移...
    }
}

// 另一种正确的遍历顺序：从下往上，从左往右
for (int l = n - 1; l >= 0; l--) {
    for (int r = l + 1; r < n; r++) {
        // 状态转移...
    }
}

class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];
        
        // 单个字符是回文，长度为1
        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }
        
        // 按区间长度递增遍历
        for (int len = 2; len <= n; len++) {
            for (int l = 0; l + len - 1 < n; l++) {
                int r = l + len - 1;
                if (s.charAt(l) == s.charAt(r)) {
                    // 两端字符相同，可以配对
                    dp[l][r] = dp[l + 1][r - 1] + 2;
                } else {
                    // 两端字符不同，取收缩后的较大值
                    dp[l][r] = Math.max(dp[l + 1][r], dp[l][r - 1]);
                }
            }
        }
        
        return dp[0][n - 1];
    }
}

class Solution {
    public int maxCoins(int[] nums) {
        int n = nums.length;
        // 添加虚拟气球
        int[] arr = new int[n + 2];
        arr[0] = 1;
        arr[n + 1] = 1;
        for (int i = 0; i < n; i++) {
            arr[i + 1] = nums[i];
        }
        
        // dp[l][r] 表示开区间 (l, r) 内的最大硬币
        int[][] dp = new int[n + 2][n + 2];
        
        // 区间长度从3开始（至少需要一个气球）
        for (int len = 3; len <= n + 2; len++) {
            for (int l = 0; l + len - 1 <= n + 1; l++) {
                int r = l + len - 1;
                // 枚举最后被戳破的气球
                for (int k = l + 1; k < r; k++) {
                    dp[l][r] = Math.max(dp[l][r], 
                        dp[l][k] + dp[k][r] + arr[l] * arr[k] * arr[r]);
                }
            }
        }
        
        return dp[0][n + 1];
    }
}

class Solution {
    public int minScoreTriangulation(int[] values) {
        int n = values.length;
        int[][] dp = new int[n][n];
        
        // 区间长度从3开始（三角形至少需要3个顶点）
        for (int len = 3; len <= n; len++) {
            for (int l = 0; l + len - 1 < n; l++) {
                int r = l + len - 1;
                dp[l][r] = Integer.MAX_VALUE;
                // 枚举第三个顶点
                for (int k = l + 1; k < r; k++) {
                    dp[l][r] = Math.min(dp[l][r], 
                        dp[l][k] + dp[k][r] + values[l] * values[k] * values[r]);
                }
            }
        }
        
        return dp[0][n - 1];
    }
}

class Solution {
    public int minInsertions(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];
        
        // 从下往上，从左往右填充
        for (int l = n - 2; l >= 0; l--) {
            for (int r = l + 1; r < n; r++) {
                if (s.charAt(l) == s.charAt(r)) {
                    dp[l][r] = dp[l + 1][r - 1];
                } else {
                    dp[l][r] = Math.min(dp[l + 1][r], dp[l][r - 1]) + 1;
                }
            }
        }
        
        return dp[0][n - 1];
    }
}

class Solution {
    private Boolean[][][] memo;
    private String s1, s2;
    
    public boolean isScramble(String s1, String s2) {
        int n = s1.length();
        this.s1 = s1;
        this.s2 = s2;
        memo = new Boolean[n][n][n + 1];
        return dfs(0, 0, n);
    }
    
    private boolean dfs(int i, int j, int len) {
        if (memo[i][j][len] != null) {
            return memo[i][j][len];
        }
        
        // 长度为1，直接比较字符
        if (len == 1) {
            return s1.charAt(i) == s2.charAt(j);
        }
        
        // 剪枝：字符频率必须相同
        int[] count = new int[26];
        for (int k = 0; k < len; k++) {
            count[s1.charAt(i + k) - 'a']++;
            count[s2.charAt(j + k) - 'a']--;
        }
        for (int c : count) {
            if (c != 0) {
                memo[i][j][len] = false;
                return false;
            }
        }
        
        // 枚举分割点
        for (int k = 1; k < len; k++) {
            // 不交换
            if (dfs(i, j, k) && dfs(i + k, j + k, len - k)) {
                memo[i][j][len] = true;
                return true;
            }
            // 交换
            if (dfs(i, j + len - k, k) && dfs(i + k, j, len - k)) {
                memo[i][j][len] = true;
                return true;
            }
        }
        
        memo[i][j][len] = false;
        return false;
    }
}

// 通用区间DP模板
for (int len = 最小长度; len <= n; len++) {
    for (int l = 0; l + len - 1 < n; l++) {
        int r = l + len - 1;
        if (len == 最小长度) {
            // 边界条件
            dp[l][r] = 基础值;
        } else {
            // 枚举分割点
            for (int k = l; k < r; k++) {
                dp[l][r] = 最优(dp[l][r], dp[l][k] 与 dp[k+1][r] 的组合);
            }
            // 或根据端点关系收缩
            if (条件) {
                dp[l][r] = dp[l+1][r-1] + 增量;
            } else {
                dp[l][r] = 最优(dp[l+1][r], dp[l][r-1]);
            }
        }
    }
}