动态规划入门

什么是动态规划？

动态规划（Dynamic Programming，DP）是一种通过把原问题分解为相互重叠的子问题来求解最优化问题的方法。

DP 的两个核心特征：

1. 最优子结构：问题的最优解可以由子问题的最优解构造
2. 重叠子问题：在求解过程中，相同的子问题被多次求解

与分治法的区别：分治法的子问题相互独立（归并排序），DP 的子问题相互重叠（斐波那契数列）。

从暴力递归到动态规划

以斐波那契数列为例，展示 DP 的演进过程。

1. 暴力递归（指数时间）

int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);  // 大量重复计算
}

fib(5) 的递归树（括号里是重复计算的）：
                    fib(5)
                   /       \
              fib(4)        fib(3)
             /    \        /    \
          fib(3)  fib(2) fib(2)  fib(1)
          /  \
       fib(2) fib(1)

fib(3) 被算了 2 次，fib(2) 被算了 3 次。时间复杂度 O(2^n)。

2. 记忆化递归（Top-Down DP）

int[] memo;

int fib(int n) {
    memo = new int[n + 1];
    Arrays.fill(memo, -1);
    return helper(n);
}

int helper(int n) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];   // 命中缓存
    memo[n] = helper(n - 1) + helper(n - 2);
    return memo[n];
}

每个子问题只算一次，时间复杂度降至 O(n)，空间 O(n)（递归栈）。

3. 递推（Bottom-Up DP）

int fib(int n) {
    if (n <= 1) return n;
    int[] dp = new int[n + 1];
    dp[0] = 0; dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];   // 从小到大填表
    }
    return dp[n];
}

4. 空间优化（滚动数组）

int fib(int n) {
    if (n <= 1) return n;
    int prev = 0, curr = 1;
    for (int i = 2; i <= n; i++) {
        int next = prev + curr;
        prev = curr;
        curr = next;
    }
    return curr;
}

只用两个变量，空间降至 O(1)。

解题框架

DP 解题的核心步骤：

第一步：定义状态
dp[i] 或 dp[i][j] 代表什么含义？

第二步：确定状态转移方程
dp[i] 如何从之前的状态推导出来？

第三步：确定初始化（基础情况）
最小子问题的答案是什么？

第四步：确定计算顺序
保证计算 dp[i] 时，它依赖的状态都已经算好。

经典 DP：爬楼梯

问题：爬 n 阶楼梯，每次可爬 1 或 2 阶，共有多少种方法？

n=1: 1 种（1）
n=2: 2 种（1+1, 2）
n=3: 3 种（1+1+1, 1+2, 2+1）

状态定义：dp[i] = 爬到第 i 阶的方法数

转移方程：最后一步要么从 i-1 来，要么从 i-2 来： dp[i] = dp[i-1] + dp[i-2]

初始化：dp[1] = 1, dp[2] = 2

int climbStairs(int n) {
    if (n <= 2) return n;
    int prev = 1, curr = 2;
    for (int i = 3; i <= n; i++) {
        int next = prev + curr;
        prev = curr;
        curr = next;
    }
    return curr;
}

经典 DP：最大子数组和（Kadane 算法）

问题：给定整数数组，找连续子数组的最大和。

状态定义：dp[i] = 以 nums[i] 结尾的连续子数组的最大和

关键洞察：以 nums[i] 结尾的子数组，要么只包含 nums[i]（前面的都不要），要么在前面最优子数组基础上扩展（如果 dp[i-1] > 0）。

int maxSubArray(int[] nums) {
    int dp = nums[0];           // dp[i] 的滚动变量
    int maxSum = nums[0];

    for (int i = 1; i < nums.length; i++) {
        dp = Math.max(nums[i], dp + nums[i]);  // 要么重新开始，要么继续扩展
        maxSum = Math.max(maxSum, dp);
    }
    return maxSum;
}

经典 DP：0/1 背包

问题：n 个物品，每个有重量 w[i] 和价值 v[i]，背包容量为 W，求最大价值。每个物品只能选一次（0/1背包）。

状态定义：dp[i][j] = 前 i 个物品中，背包容量为 j 时的最大价值

转移方程：对于第 i 个物品：

• 不选：dp[i][j] = dp[i-1][j]
• 选（需要 j ≥ w[i]）：dp[i][j] = dp[i-1][j-w[i]] + v[i]
• 取两者最大值

int knapsack(int[] w, int[] v, int W) {
    int n = w.length;
    int[][] dp = new int[n + 1][W + 1];
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= W; j++) {
            dp[i][j] = dp[i - 1][j];                     // 不选
            if (j >= w[i - 1]) {
                dp[i][j] = Math.max(dp[i][j],
                    dp[i - 1][j - w[i - 1]] + v[i - 1]); // 选
            }
        }
    }
    return dp[n][W];
}

空间优化（滚动数组）：注意 j 必须从大到小遍历，防止同一物品被选多次：

int knapsack(int[] w, int[] v, int W) {
    int[] dp = new int[W + 1];
    for (int i = 0; i < w.length; i++) {
        for (int j = W; j >= w[i]; j--) {   // 从右往左！
            dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    return dp[W];
}

经典 DP：最长公共子序列（LCS）

问题：给定两个字符串 s1、s2，找最长公共子序列的长度（子序列不要求连续）。

状态定义：dp[i][j] = s1 的前 i 个字符和 s2 的前 j 个字符的最长公共子序列长度

转移方程：

• 若 s1[i-1] == s2[j-1]：dp[i][j] = dp[i-1][j-1] + 1（两者配对）
• 否则：dp[i][j] = max(dp[i-1][j], dp[i][j-1])（各退一步取最大）

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：最长递增子序列（LIS）

问题：找数组中最长的严格递增子序列的长度。

O(n²) DP：

int lengthOfLIS(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];  // dp[i] = 以 nums[i] 结尾的 LIS 长度
    Arrays.fill(dp, 1);     // 最少长度为 1（只有自己）
    int maxLen = 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);
            }
        }
        maxLen = Math.max(maxLen, dp[i]);
    }
    return maxLen;
}

O(n log n) 贪心 + 二分：维护一个"最优末尾"数组 tails，tails[i] 是长度为 i+1 的递增子序列中，末尾元素的最小值。

int lengthOfLIS(int[] nums) {
    int[] tails = new int[nums.length];
    int size = 0;
    for (int num : nums) {
        int lo = 0, hi = size;
        while (lo < hi) {               // 找第一个 >= num 的位置
            int mid = lo + (hi - lo) / 2;
            if (tails[mid] < num) lo = mid + 1;
            else hi = mid;
        }
        tails[lo] = num;                // 替换或扩展
        if (lo == size) size++;
    }
    return size;
}

DP 的常见类型

小结

DP 思维的本质：

1. 识别 DP 问题：最优解、计数、是否可行 + 有重叠子问题
2. 定义状态：dp 数组的含义是什么？（最重要的一步）
3. 状态转移：大问题如何从小问题转移？
4. 初始化：边界条件（n=0 或 n=1 时）
5. 计算顺序：保证求 dp[i] 时依赖的状态已计算

Top-Down（记忆化）vs. Bottom-Up（递推）：

• Top-Down 更直观，直接翻译递归定义，但有递归栈开销
• Bottom-Up 更高效，可以进一步优化空间，推荐优先掌握