高频算法题型：动态规划三步法

高频算法题型：动态规划三步法是计算机科学的核心，它为问题解决提供了高效的计算方法。
本文介绍了高频算法题型：动态规划三步法的设计思路和实现方式，帮助你提升编程能力。

动态规划的核心思想：将复杂问题拆成子问题，记录子问题的解避免重复计算。

能用 DP 解决的问题必须满足两个条件：

1. 最优子结构：大问题的最优解包含子问题的最优解
2. 无后效性：当前状态确定后，未来的演化不受过去路径影响

1.2 动态规划三步法

第一步：定义状态 —— dp 数组每个元素代表什么？
第二步：推导转移方程 —— dp[i] 怎么从之前的值算出来？
第三步：确定初始条件和边界 —— dp[0] 是什么？越界怎么处理？

这三步是解题的灵魂。 只要三步走对了，代码自然就出来了。

二、一维 DP

第 1 题：爬楼梯（LeetCode 70）

题目： 每次爬 1 或 2 步，爬到 n 阶有多少种方法？

三步法：

1. 状态：dp[i] = 爬到第 i 阶的方法数
2. 转移：dp[i] = dp[i-1] + dp[i-2]（最后一步爬 1 或 2 步）
3. 初始：dp[0] = 1, dp[1] = 1

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

// 空间优化版
public int climbStairsOptimized(int n) {
    if (n <= 1) return 1;
    int prev2 = 1, prev1 = 1;
    for (int i = 2; i <= n; i++) {
        int curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

第 2 题：打家劫舍（LeetCode 198）

题目： 偷沿街房屋，不能偷相邻的，求最大金额。

三步法：

1. 状态：dp[i] = 前 i 间房屋能偷的最大金额
2. 转移：dp[i] = max(dp[i-1], dp[i-2] + nums[i])（偷或不偷第 i 间）
3. 初始：dp[0] = nums[0], dp[1] = max(nums[0], nums[1])

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

第 3 题：最大子数组和（LeetCode 53）

题目： 找到和最大的连续子数组。

三步法：

1. 状态：dp[i] = 以 nums[i] 结尾的最大子数组和
2. 转移：dp[i] = max(dp[i-1] + nums[i], nums[i])（延续 or 重新开始）
3. 初始：dp[0] = nums[0]

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

// 空间优化
public int maxSubArrayOptimized(int[] nums) {
    int prev = nums[0], maxSum = nums[0];
    for (int i = 1; i < nums.length; i++) {
        prev = Math.max(prev + nums[i], nums[i]);
        maxSum = Math.max(maxSum, prev);
    }
    return maxSum;
}

第 4 题：最长递增子序列（LeetCode 300）

题目： 找到最长严格递增子序列长度。

三步法：

1. 状态：dp[i] = 以 nums[i] 结尾的 LIS 长度
2. 转移：dp[i] = max(dp[j] + 1) for all j < i where nums[j] < nums[i]
3. 初始：dp[i] = 1（每个元素自身长度为 1）

public 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[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        maxLen = Math.max(maxLen, dp[i]);
    }
    return maxLen;
}

复杂度： O(n²)。可以用二分查找优化到 O(n log n)：

public int lengthOfLISBinary(int[] nums) {
    int[] tails = new int[nums.length];
    int size = 0;
    for (int num : nums) {
        int left = 0, right = size;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (tails[mid] < num) left = mid + 1;
            else right = mid;
        }
        tails[left] = num;
        if (left == size) size++;
    }
    return size;
}

第 5 题：零钱兑换（LeetCode 322）

题目： 给定硬币面值，凑成目标金额的最少硬币数。

三步法：

1. 状态：dp[i] = 凑成金额 i 的最少硬币数
2. 转移：dp[i] = min(dp[i - coin] + 1) for each coin
3. 初始：dp[0] = 0，其余初始化为 Integer.MAX_VALUE

public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1); // 用 amount+1 代替 MAX_VALUE 避免溢出
    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];
}

三、二维 DP

第 6 题：不同路径（LeetCode 62）

题目： 从左上角走到右下角有多少条路径（只能向右或向下）。

三步法：

1. 状态：dp[i][j] = 到达位置 (i,j) 的路径数
2. 转移：dp[i][j] = dp[i-1][j] + dp[i][j-1]
3. 初始：dp[0][j] = 1, dp[i][0] = 1（第一行和第一列只有一种路径）

public int uniquePaths(int m, int n) {
    int[][] dp = new int[m][n];
    
    for (int i = 0; i < m; i++) dp[i][0] = 1;
    for (int j = 0; j < n; j++) dp[0][j] = 1;
    
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    return dp[m - 1][n - 1];
}

第 7 题：最长公共子序列（LeetCode 1143）

题目： 找两个字符串的最长公共子序列长度。

三步法：

1. 状态：dp[i][j] = text1 前 i 个字符和 text2 前 j 个字符的 LCS 长度
2. 转移：
   • 如果 text1[i-1] == text2[j-1]：dp[i][j] = dp[i-1][j-1] + 1
   • 否则：dp[i][j] = max(dp[i-1][j], dp[i][j-1])
3. 初始：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];
}

第 8 题：编辑距离（LeetCode 72）

题目： 将 word1 转换成 word2 的最少操作次数（插入/删除/替换）。

三步法：

1. 状态：dp[i][j] = word1 前 i 个字符转成 word2 前 j 个字符的最少操作数
2. 转移：
   • 如果 word1[i-1] == word2[j-1]：dp[i][j] = dp[i-1][j-1]（不用操作）
   • 否则：dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])（替换/删除/插入）
3. 初始：dp[i][0] = i（删除 i 个字符），dp[0][j] = 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] = 1 + Math.min(
                    dp[i - 1][j - 1],  // 替换
                    Math.min(
                        dp[i - 1][j],   // 删除 word1 的字符
                        dp[i][j - 1]    // 插入 word2 的字符
                    )
                );
            }
        }
    }
    return dp[m][n];
}

第 9 题：0-1 背包问题

题目： N 个物品，每个有重量和价值，背包容量 W，求最大价值。

三步法：

1. 状态：dp[i][w] = 前 i 个物品，容量 w 时的最大价值
2. 转移：
   • 不放第 i 个物品：dp[i][w] = dp[i-1][w]
   • 放第 i 个物品：dp[i][w] = dp[i-1][w-weight[i]] + value[i]
   • 取最大值
3. 初始：dp[0][w] = 0

public int knapsack01(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 w = 0; w <= capacity; w++) {
            dp[i][w] = dp[i - 1][w]; // 不放
            if (w >= weights[i - 1]) {
                dp[i][w] = Math.max(dp[i][w], 
                    dp[i - 1][w - weights[i - 1]] + values[i - 1]);
            }
        }
    }
    return dp[n][capacity];
}

// 一维空间优化（逆序遍历！）
public int knapsack01Optimized(int[] weights, int[] values, int capacity) {
    int[] dp = new int[capacity + 1];
    for (int i = 0; i < weights.length; i++) {
        for (int w = capacity; w >= weights[i]; w--) { // 逆序！
            dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }
    return dp[capacity];
}

避坑： 一维背包必须逆序遍历！正序会导致一个物品被重复选取（变成完全背包）。

第 10 题：分割等和子集（LeetCode 416）

题目： 判断数组能否分成两个和相等的子集。

转化为 0-1 背包： 背包容量 = sum/2，看能否刚好装满。

public boolean canPartition(int[] nums) {
    int sum = 0;
    for (int num : nums) sum += num;
    if (sum % 2 != 0) return false;
    
    int target = sum / 2;
    boolean[] dp = new boolean[target + 1];
    dp[0] = true;
    
    for (int num : nums) {
        for (int j = target; j >= num; j--) { // 逆序
            dp[j] = dp[j] || dp[j - num];
        }
    }
    return dp[target];
}

四、区间 DP

第 11 题：最长回文子串（LeetCode 5）

三步法：

1. 状态：dp[i][j] = s[i..j] 是否是回文
2. 转移：dp[i][j] = (s[i] == s[j]) && dp[i+1][j-1]
3. 初始：dp[i][i] = true，dp[i][i+1] = (s[i] == s[i+1])

public String longestPalindrome(String s) {
    int n = s.length();
    boolean[][] dp = new boolean[n][n];
    int start = 0, maxLen = 1;
    
    // 单个字符都是回文
    for (int i = 0; i < n; i++) dp[i][i] = true;
    
    // 从短到长枚举所有子串
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            if (s.charAt(i) == s.charAt(j)) {
                if (len == 2 || dp[i + 1][j - 1]) {
                    dp[i][j] = true;
                    if (len > maxLen) {
                        start = i;
                        maxLen = len;
                    }
                }
            }
        }
    }
    return s.substring(start, start + maxLen);
}

第 12 题：最长回文子序列（LeetCode 516）

三步法：

1. 状态：dp[i][j] = s[i..j] 最长回文子序列长度
2. 转移：
   • s[i] == s[j]：dp[i][j] = dp[i+1][j-1] + 2
   • s[i] != s[j]：dp[i][j] = max(dp[i+1][j], dp[i][j-1])
3. 初始：dp[i][i] = 1

public int longestPalindromeSubseq(String s) {
    int n = s.length();
    int[][] dp = new int[n][n];
    
    for (int i = n - 1; i >= 0; i--) {
        dp[i][i] = 1;
        for (int j = i + 1; j < n; j++) {
            if (s.charAt(i) == s.charAt(j)) {
                dp[i][j] = dp[i + 1][j - 1] + 2;
            } else {
                dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[0][n - 1];
}

第 13 题：戳气球（LeetCode 312）

题目： n 个气球，戳破气球 i 获得 nums[i-1]*nums[i]*nums[i+1] 分，求最大得分。

三步法：

1. 状态：dp[i][j] = 戳破开区间 (i,j) 内所有气球的最大得分
2. 转移：dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j]) for k in (i,j)
3. 初始：dp[i][i+1] = 0（相邻之间没有气球）

public int maxCoins(int[] nums) {
    int n = nums.length;
    int[] arr = new int[n + 2];
    arr[0] = arr[n + 1] = 1;
    System.arraycopy(nums, 0, arr, 1, n);
    
    int[][] dp = new int[n + 2][n + 2];
    
    // 从短区间到长区间
    for (int len = 3; len <= n + 2; len++) {
        for (int i = 0; i + len - 1 <= n + 1; i++) {
            int j = i + len - 1;
            for (int k = i + 1; k < j; k++) {
                dp[i][j] = Math.max(dp[i][j],
                    dp[i][k] + dp[k][j] + arr[i] * arr[k] * arr[j]);
            }
        }
    }
    return dp[0][n + 1];
}

核心思路： 反向思考——不先戳哪个，而是最后戳哪个。假设 k 是 (i,j) 中最后戳的，则左边 (i,k) 和右边 (k,j) 已经戳完。

五、更多经典题

第 14 题：单词拆分（LeetCode 139）

三步法：

1. 状态：dp[i] = s[0..i-1] 能否被字典拼出
2. 转移：dp[i] = true if exists j where dp[j] && s[j..i-1] in dict
3. 初始：dp[0] = true

public boolean wordBreak(String s, List<String> wordDict) {
    Set<String> dict = new HashSet<>(wordDict);
    int n = s.length();
    boolean[] dp = new boolean[n + 1];
    dp[0] = true;
    
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j] && dict.contains(s.substring(j, i))) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[n];
}

第 15 题：打家劫舍 III（LeetCode 337）

题目： 二叉树结构，不能偷相邻节点，求最大金额。

树形 DP：

public int rob(TreeNode root) {
    int[] result = dfs(root);
    return Math.max(result[0], result[1]);
}

// 返回 [不偷当前节点的最大值, 偷当前节点的最大值]
private int[] dfs(TreeNode node) {
    if (node == null) return new int[]{0, 0};
    
    int[] left = dfs(node.left);
    int[] right = dfs(node.right);
    
    // 不偷当前：左右子树各自偷或不偷的最大值之和
    int notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
    // 偷当前：当前值 + 左右子树不偷
    int rob = node.val + left[0] + right[0];
    
    return new int[]{notRob, rob};
}

六、DP 题型分类速查表

类型	特征	代表题
一维 DP	线性递推	爬楼梯、打家劫舍、LIS
二维 DP	两个序列/网格	LCS、编辑距离、背包
区间 DP	枚举区间和分界点	回文子串、戳气球
树形 DP	在树上做 DP	打家劫舍 III
状态压缩 DP	用位运算表示状态	旅行商问题
背包问题	选/不选物品	0-1背包、完全背包

七、面试要点与总结

高频面试题

Q1：DP 和贪心的区别？

答：DP 考虑所有子问题的最优解来推导全局最优；贪心只做当下最优选择不回退。DP 更通用但复杂度高，贪心更快但需要证明贪心选择的正确性。

Q2：0-1 背包的一维优化为什么要逆序？

答：一维 DP 中 dp[w] 依赖 dp[w-weight]。如果正序遍历，dp[w-weight] 可能已经包含了当前物品（被选过了），导致一个物品被重复选取。逆序保证 dp[w-weight] 还是上一轮的值。

Q3：编辑距离的三个操作分别对应什么？

答：dp[i-1][j-1] → 替换（改一个字符）；dp[i-1][j] → 删除 word1 的字符；dp[i][j-1] → 插入 word2 的字符。

Q4：区间 DP 为什么要按长度枚举？

答：区间 DP 的转移方程通常依赖更短的子区间。按长度从小到大枚举，保证计算当前区间时子区间已经算好了。

Q5：什么时候用记忆化搜索（自顶向下），什么时候用递推（自底向上）？

答：面试中优先用递推（迭代），不容易栈溢出，效率更高。如果状态转移难以按顺序枚举（如某些区间 DP），用记忆化搜索更直观。

总结

动态规划解题三板斧：

1. 定义状态：dp 数组代表什么？
   → 想清楚"问什么就定义什么"

2. 转移方程：怎么从已知推出未知？
   → 想清楚"最后一步做了什么选择"

3. 初始条件：最小的子问题答案是什么？
   → dp[0] 或 dp[0][0] 通常是边界

写代码的通用流程：

1. 初始化 dp 数组
2. 设置初始条件
3. 按顺序填表（一维从左到右，二维注意遍历方向）
4. 返回结果

一句话总结： 动态规划的本质是「记住已经算过的答案」。三步法定义好状态后，转移方程就是"最后一步的选择"——想清楚最后一步怎么走，整个 DP 就通了。