动态规划

什么是 DP？

动态规划（Dynamic Programming）是将复杂问题分解成子问题，通过保存子问题的解来避免重复计算。

核心思想

1. 最优子结构 - 问题的最优解包含子问题的最优解
2. 重叠子问题 - 子问题会被重复计算
3. 状态转移方程 - 定义如何从子问题得到原问题的解

经典问题

1. 爬楼梯

每次可以爬 1 或 2 阶，问爬到 n 阶有多少种方法

// dp[i] = 爬到第 i 阶的方法数
// dp[i] = dp[i-1] + dp[i-2]

int climbStairs(int n) {
    if (n <= 2) return n;
    int[] dp = new int[n + 1];
    dp[1] = 1;
    dp[2] = 2;
    
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

2. 最长递增子序列（LIS）

int lengthOfLIS(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);
    
    int maxLen = 1;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        maxLen = Math.max(maxLen, dp[i]);
    }
    return maxLen;
}

3. 背包问题

// 0-1 背包
// dp[i][w] = 前 i 个物品，容量为 w 时的最大价值

int knapsack(int[] weight, int[] value, int W) {
    int n = weight.length;
    int[] dp = new int[W + 1];
    
    for (int i = 0; i < n; i++) {
        for (int w = W; w >= weight[i]; w--) {
            dp[w] = Math.max(dp[w], dp[w - weight[i]] + value[i]);
        }
    }
    return dp[W];
}

DP 解题套路

1. 定义状态 - 确定 dp 数组的含义
2. 状态转移 - 找出递推关系
3. 初始化 - 确定边界条件
4. 遍历顺序 - 确定计算顺序
5. 返回结果 - 从 dp 数组得到答案

更多经典问题

• 股票买卖系列
• 编辑距离
• 最长公共子序列
• 矩阵路径问题