跳到主要内容

动态规划

问题​

什么是动态规划？如何分析 DP 问题？

答案​

核心步骤​

  1. 定义状态：dp[i] 表示什么含义
  2. 状态转移方程：dp[i] 如何从之前的状态推导
  3. 初始化：边界条件
  4. 遍历顺序：确保计算 dp[i] 时所依赖的状态已经计算过

爬楼梯（入门）​

爬楼梯：dp[i] = dp[i-1] + dp[i-2]
public int climbStairs(int n) {
    if (n <= 2) return n;
    int a = 1, b = 2;
    for (int i = 3; i <= n; i++) {
        int c = a + b;  // 到第 i 级 = 从 i-1 跨 1 步 + 从 i-2 跨 2 步
        a = b;
        b = c;
    }
    return b;
}

最长递增子序列（LIS）​

LIS：dp[i] = 以 nums[i] 结尾的最长递增子序列长度
public int lengthOfLIS(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);  // 每个元素自身就是长度 1
    int max = 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);
            }
        }
        max = Math.max(max, dp[i]);
    }
    return max;  // O(n²)
}

0-1 背包​

0-1 背包：每件物品选或不选
// weight[i] = 第 i 件物品的重量，value[i] = 价值
// capacity = 背包容量
public int knapsack(int[] weight, int[] value, int capacity) {
    int n = weight.length;
    // dp[j] = 容量为 j 的背包能装的最大价值
    int[] dp = new int[capacity + 1];
    
    for (int i = 0; i < n; i++) {
        // 倒序遍历：保证每件物品只选一次
        for (int j = capacity; j >= weight[i]; j--) {
            dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    return dp[capacity];
}

零钱兑换（完全背包）​

零钱兑换：凑出 amount 的最少硬币数
public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);  // 初始化为不可能的大值
    dp[0] = 0;
    
    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (coin <= i) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

最长公共子序列（LCS）​

LCS
public int longestCommonSubsequence(String text1, String text2) {
    int m = text1.length(), n = text2.length();
    int[][] dp = new int[m + 1][n + 1];
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1.charAt(i - 1) == text2.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];
}

常见面试问题​

Q1: 动态规划和贪心的区别？​

答案：

维度动态规划贪心
选择策略考虑所有可能，选最优每步选局部最优
子问题有重叠子问题无后效性
正确性一定最优不一定最优（需要证明）
效率较慢（需要存储状态表）快

Q2: DP 问题的通用解题模板？​

答案：

  1. 能不能用 DP？→ 最优子结构 + 重叠子问题
  2. 定义 dp[i]（或 dp[i][j]）的含义
  3. 找状态转移方程
  4. 确定初始条件和边界
  5. 确定遍历顺序
  6. 用实例验证

相关链接​