动态规划（Dynamic Programming）

动态规划（Dynamic Programming）详解

1. 引言

动态规划（Dynamic Programming，简称DP）是算法面试中的常客，也是很多初学者觉得头疼的难点。它的思想其实并不复杂，核心是“记住已经解决过的子问题的解，避免重复计算”。本文将从动态规划的基本概念出发，梳理其通用解题模板，并通过几个经典案例，带你彻底掌握动态规划。

2. 什么是动态规划？

动态规划是一种通过把原问题分解为相对简单的子问题，并保存子问题的解来避免重复计算的方法。它通常适用于具有以下两个性质的问题：

• 最优子结构：一个问题的最优解包含其子问题的最优解。即可以通过子问题的最优解推导出原问题的最优解。
• 重叠子问题：在求解过程中，会反复地求解相同的子问题。如果采用递归，会导致大量的重复计算，而动态规划通过存储子问题的结果，使得每个子问题只计算一次。

动态规划与分治法的区别：分治法也分解子问题，但子问题通常是不重叠的（如归并排序）；而动态规划处理的是重叠子问题。
动态规划与贪心算法的区别：贪心算法只考虑当前局部最优，不保证全局最优；而动态规划会考虑所有可能的决策，保证全局最优。

3. 动态规划的解题步骤

动态规划通常可以按照以下四个步骤思考：

1. 定义状态：明确dp数组的含义，即dp[i]或dp[i][j]代表什么。
2. 初始化：确定base case，即最小子问题的解。
3. 状态转移方程：找出dp[i]与前面项的关系，这是最核心的一步。
4. 确定遍历顺序：根据状态转移方程，决定是从前往后还是从后往前，或者多维的顺序。
5. 返回最终结果：通常返回dp[n]或dp[m][n]等。

4. 经典案例

4.1 斐波那契数列

题目：求斐波那契数列的第n项（f(0)=0, f(1)=1, f(n)=f(n-1)+f(n-2)）。

这是最简单的动态规划入门题，直接体现了重叠子问题。

public 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];
}

优化：由于只依赖前两个状态，可以用滚动变量将空间复杂度降到O(1)。

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

4.2 爬楼梯问题

题目：假设你正在爬楼梯，需要n阶才能到达楼顶。每次你可以爬1或2个台阶，问有多少种不同的方法可以爬到楼顶？

分析：到达第i阶的方法数 = 到达第i-1阶的方法数 + 到达第i-2阶的方法数。因为从i-1跨1步，或从i-2跨2步。这就是一个斐波那契数列的变种。

public 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];
}

4.3 最大子数组和（LeetCode 53）

题目：给定一个整数数组 nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

状态定义：dp[i]表示以第i个元素结尾的连续子数组的最大和。

状态转移：对于dp[i]，要么将nums[i]加入前一个子数组（dp[i-1] + nums[i]），要么重新开始（nums[i]）。取两者最大值。
即：dp[i] = max(dp[i-1] + nums[i], nums[i])。

最终结果：所有dp[i]中的最大值。

public int maxSubArray(int[] nums) {
    int[] dp = new int[nums.length];
    dp[0] = nums[0];
    int maxSum = dp[0];
    for (int i = 1; i < nums.length; i++) {
        dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
        maxSum = Math.max(maxSum, dp[i]);
    }
    return maxSum;
}

4.4 0-1背包问题

题目：有N件物品和一个容量为V的背包。每件物品有重量w[i]和价值v[i]。求解将哪些物品装入背包可使价值总和最大，每种物品最多只能用一次。

状态定义：dp[i][j]表示前i件物品放入容量为j的背包中所能获得的最大价值。

状态转移：对于第i件物品，有两种选择：

• 不放入：dp[i][j] = dp[i-1][j]
• 放入：dp[i][j] = dp[i-1][j - w[i]] + v[i]（前提是j >= w[i]）

取两者较大值。
dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i])

初始化：dp[0][j] = 0，dp[i][0] = 0。

空间优化：可以用一维数组，但要注意内层循环从大到小，防止覆盖。

public int knapsack(int[] weights, int[] values, int capacity) {
    int n = weights.length;
    int[][] dp = new int[n + 1][capacity + 1];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= capacity; j++) {
            if (j < weights[i - 1]) {
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = Math.max(dp[i - 1][j],
                        dp[i - 1][j - weights[i - 1]] + values[i - 1]);
            }
        }
    }
    return dp[n][capacity];
}

// 一维优化
public int knapsackOptimized(int[] weights, int[] values, int capacity) {
    int n = weights.length;
    int[] dp = new int[capacity + 1];
    for (int i = 0; i < n; i++) {
        for (int j = capacity; j >= weights[i]; j--) {
            dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }
    return dp[capacity];
}

4.5 最长公共子序列（LCS）

题目：给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

状态定义：dp[i][j]表示text1的前i个字符与text2的前j个字符的最长公共子序列长度。

状态转移：

• 如果 text1.charAt(i-1) == text2.charAt(j-1)，则 dp[i][j] = dp[i-1][j-1] + 1
• 否则，dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])

初始化：dp[0][j] = 0，dp[i][0] = 0。

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];
}

4.6 编辑距离（LeetCode 72）

题目：给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数。操作包括：插入、删除、替换一个字符。

状态定义：dp[i][j]表示word1的前i个字符转换成word2的前j个字符所需的最少操作数。

状态转移：

• 如果 word1.charAt(i-1) == word2.charAt(j-1)，则 dp[i][j] = dp[i-1][j-1]
• 否则，考虑三种操作：
  • 插入：dp[i][j-1] + 1
  • 删除：dp[i-1][j] + 1
  • 替换：dp[i-1][j-1] + 1
    取三者最小值。

初始化：dp[i][0] = i（删除所有字符），dp[0][j] = j（插入所有字符）。

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;
    for (int j = 0; j <= n; j++) dp[0][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] = Math.min(dp[i - 1][j - 1],
                        Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
            }
        }
    }
    return dp[m][n];
}

5. 动态规划的进阶技巧

• 状态压缩：当dp只依赖前一行或前几行时，可以用滚动数组减少空间。
• 记忆化搜索：有时用递归+备忘录的方式更容易理解，本质也是动态规划。
• 区间DP：例如石子合并问题，状态通常定义为dp[i][j]表示区间[i,j]的最优解。
• 树形DP：在树上进行动态规划，例如二叉树的最大路径和。

6. 总结

动态规划是一种通过空间换时间的技术，核心在于定义好状态并推导出状态转移方程。