动态规划：状态定义、转移与空间压缩

动态规划的本质

动态规划（Dynamic Programming，DP） 适用于有重叠子问题和最优子结构的问题。

DP = 递归 + 记忆化（自顶向下）
DP = 填表（自底向上） 

与分治的区别：DP 的子问题之间有重叠，需要缓存；分治的子问题相互独立。

DP 四步法

1. 定义状态 dp[i]（或 dp[i][j]）的含义
2. 推导状态转移方程（大问题 → 小问题）
3. 确定边界条件（初始值）
4. 确定计算顺序，实现填表

线性 DP

最长递增子序列（LIS）

// O(n²) - 经典 DP
// dp[i] = 以 nums[i] 结尾的 LIS 长度
public int lengthOfLIS(int[] nums) {
    int n = nums.length, ans = 1;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        ans = Math.max(ans, dp[i]);
    }
    return ans;
}

// O(n log n) - 贪心 + 二分
public int lengthOfLIS_fast(int[] nums) {
    List<Integer> tails = new ArrayList<>();
    for (int x : nums) {
        int pos = Collections.binarySearch(tails, x);
        if (pos < 0) pos = -(pos + 1);
        if (pos == tails.size()) tails.add(x);
        else tails.set(pos, x);
    }
    return tails.size();
}

最大子数组和（Kadane 算法）

// dp[i] = 以 nums[i] 结尾的最大子数组和
// 转移：dp[i] = max(dp[i-1] + nums[i], nums[i])
//      = nums[i] + max(dp[i-1], 0)
public int maxSubArray(int[] nums) {
    int dp = nums[0], ans = nums[0];
    for (int i = 1; i < nums.length; i++) {
        dp = nums[i] + Math.max(dp, 0);
        ans = Math.max(ans, dp);
    }
    return ans;
}

二维 DP

最长公共子序列（LCS）

// dp[i][j] = s1[0..i-1] 和 s2[0..j-1] 的 LCS 长度
public int longestCommonSubsequence(String s1, String s2) {
    int m = s1.length(), n = s2.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n];
}

编辑距离

// dp[i][j] = word1[0..i-1] 变成 word2[0..j-1] 的最少操作数
public int minDistance(String word1, String word2) {
    int m = word1.length(), n = word2.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 0; i <= m; i++) dp[i][0] = i;  // 删除 i 次
    for (int j = 0; j <= n; j++) dp[0][j] = j;  // 插入 j 次
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + Math.min(dp[i - 1][j - 1],   // 替换
                                Math.min(dp[i - 1][j],        // 删除
                                         dp[i][j - 1]));      // 插入
            }
        }
    }
    return dp[m][n];
}

背包问题

0-1 背包

// dp[j] = 容量为 j 时的最大价值
// 必须逆序遍历（保证每件物品只用一次）
public int knapsack01(int[] weights, int[] values, int W) {
    int[] dp = new int[W + 1];
    for (int i = 0; i < weights.length; i++) {
        for (int j = W; j >= weights[i]; j--) {  // 逆序！
            dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }
    return dp[W];
}

完全背包（每件物品可无限用）

// 正序遍历（允许重复使用）
public int completeBag(int[] weights, int[] values, int W) {
    int[] dp = new int[W + 1];
    for (int i = 0; i < weights.length; i++) {
        for (int j = weights[i]; j <= W; j++) {  // 正序！
            dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }
    return dp[W];
}

分组背包（零钱兑换系列）

// LeetCode 322 零钱兑换（完全背包求最少个数）
public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);  // 初始化为不可能值
    dp[0] = 0;
    for (int coin : coins) {
        for (int j = coin; j <= amount; j++) {
            dp[j] = Math.min(dp[j], dp[j - coin] + 1);
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

区间 DP

// 戳气球 LeetCode 312
// dp[i][j] = 戳破 (i,j) 之间所有气球的最大金币
// 枚举最后一个被戳的气球 k
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[][] dp = new int[n + 2][n + 2];
    for (int len = 2; len <= n + 1; len++) {
        for (int i = 0; i <= n + 1 - len; i++) {
            int j = i + len;
            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];
}

空间压缩技巧

// 编辑距离空间压缩 O(n) → 只保留一行
public int minDistance_opt(String s1, String s2) {
    int m = s1.length(), n = s2.length();
    int[] dp = new int[n + 1];
    for (int j = 0; j <= n; j++) dp[j] = j;
    for (int i = 1; i <= m; i++) {
        int prev = dp[0]; dp[0] = i;
        for (int j = 1; j <= n; j++) {
            int tmp = dp[j];
            if (s1.charAt(i - 1) == s2.charAt(j - 1)) dp[j] = prev;
            else dp[j] = 1 + Math.min(prev, Math.min(dp[j], dp[j - 1]));
            prev = tmp;
        }
    }
    return dp[n];
}

DP 常见陷阱

1. 状态定义不清晰：dp[i] 含义模糊导致转移方程错误
2. 边界条件遗漏：dp[0]、dp[1] 需要单独处理
3. 遍历顺序错误：0-1背包必须逆序，完全背包正序
4. 返回值错误：有时不是 dp[n]，而是 max(dp[0..n])

高频动态规划工程场景