LeetCode动态规划全解析：从基础到高级应用

安全风信子

发布于 2025-11-13 14:07:16

340

文章被收录于专栏：AI SPPECHAI SPPECH

一、动态规划基础

1.1 动态规划的基本概念

动态规划（Dynamic Programming，简称DP）是一种解决复杂问题的方法，它通过将原问题分解为相对简单的子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

动态规划的核心思想是：

最优子结构：问题的最优解包含其子问题的最优解
重叠子问题：在求解过程中，会多次重复计算相同的子问题
状态转移方程：描述如何从子问题的解得到原问题的解
边界条件：最小子问题的解

1.2 动态规划与其他算法的区别

与递归的区别：动态规划通过记忆化搜索或表格法避免了重复计算
与贪心算法的区别：动态规划考虑全局最优，而贪心算法只考虑局部最优
与分治法的区别：动态规划解决的问题具有重叠子问题，而分治法解决的问题子问题是相互独立的

1.3 动态规划的解题步骤

定义状态：明确dp数组的含义
确定状态转移方程：描述状态之间的转移关系
初始化：设置初始条件和边界值
确定遍历顺序：根据状态转移方程确定遍历的顺序
计算最终结果：根据dp数组得到最终的答案

二、动态规划经典问题解析

2.1 斐波那契数列（LeetCode 509）

题目描述：斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：F(0) = 0，F(1) = 1，F(n) = F(n - 1) + F(n - 2)，其中 n > 1。

示例：输入：n = 4 输出：3 解释：F(4) = F(3) + F(2) = 2 + 1 = 3

解题思路

这是动态规划的入门问题，我们可以使用递归、记忆化递归或动态规划来解决。

方法一：递归

最简单的方法是直接根据递推公式使用递归，但这种方法会有大量的重复计算，时间复杂度为O(2^n)。

public int fib(int n) {
    if (n == 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    return fib(n - 1) + fib(n - 2);
}

方法二：记忆化递归

通过使用哈希表或数组来存储已经计算过的结果，避免重复计算，时间复杂度为O(n)。

public int fib(int n) {
    if (n == 0) {
        return 0;
    }
    int[] memo = new int[n + 1];
    return fibMemo(n, memo);
}

private int fibMemo(int n, int[] memo) {
    if (n == 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    if (memo[n] != 0) {
        return memo[n];
    }
    memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
    return memo[n];
}

方法三：动态规划

使用dp数组来存储中间结果，从底向上计算，时间复杂度为O(n)，空间复杂度为O(n)。

public int fib(int n) {
    if (n == 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    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 == 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    int prev = 0;
    int curr = 1;
    for (int i = 2; i <= n; i++) {
        int next = prev + curr;
        prev = curr;
        curr = next;
    }
    return curr;
}

2.2 爬楼梯（LeetCode 70）

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

示例：输入：n = 3 输出：3 解释：有三种方法可以爬到楼顶。

1阶 + 1阶 + 1阶
1阶 + 2阶
2阶 + 1阶

解题思路

这是一个典型的动态规划问题，我们可以定义dp[i]表示爬到第i阶楼梯的不同方法数。

状态转移方程：dp[i] = dp[i-1] + dp[i-2]

边界条件：dp[1] = 1, dp[2] = 2

public int climbStairs(int n) {
    if (n == 1) {
        return 1;
    }
    if (n == 2) {
        return 2;
    }
    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];
}

空间优化版本：

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

时间复杂度：O(n)，需要遍历一次数组。 空间复杂度：O(1)，只使用了常数级别的额外空间。

2.3 最大子数组和（LeetCode 53）

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

示例：输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

解题思路

这是一个经典的动态规划问题，我们可以定义dp[i]表示以第i个元素结尾的最大子数组和。

状态转移方程：dp[i] = max(nums[i], dp[i-1] + nums[i])

边界条件：dp[0] = nums[0]

public int maxSubArray(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    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(nums[i], dp[i - 1] + nums[i]);
        maxSum = Math.max(maxSum, dp[i]);
    }
    return maxSum;
}

空间优化版本：

public int maxSubArray(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    int n = nums.length;
    int currSum = nums[0];
    int maxSum = nums[0];
    for (int i = 1; i < n; i++) {
        currSum = Math.max(nums[i], currSum + nums[i]);
        maxSum = Math.max(maxSum, currSum);
    }
    return maxSum;
}

时间复杂度：O(n)，需要遍历一次数组。 空间复杂度：O(1)，只使用了常数级别的额外空间。

2.4 零钱兑换（LeetCode 322）

题目描述：给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1 。

示例：输入：coins = [1, 2, 5], amount = 11 输出：3 解释：11 = 5 + 5 + 1

解题思路

这是一个典型的完全背包问题，我们可以定义dp[i]表示凑成总金额i所需的最少硬币个数。

状态转移方程：dp[i] = min(dp[i], dp[i-coin] + 1)，其中coin是硬币的面额

边界条件：dp[0] = 0，其余初始化为一个较大的值

public int coinChange(int[] coins, int amount) {
    if (amount == 0) {
        return 0;
    }
    if (coins == null || coins.length == 0) {
        return -1;
    }
    int[] dp = new int[amount + 1];
    // 初始化dp数组为一个较大的值
    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];
}

时间复杂度：O(amount * n)，其中n是硬币的种类数。需要填充amount大小的dp数组，每个位置需要遍历n种硬币。 空间复杂度：O(amount)，需要一个大小为amount+1的dp数组。

2.5 最长递增子序列（LeetCode 300）

题目描述：给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

示例：输入：nums = [10,9,2,5,3,7,101,18] 输出：4 解释：最长的递增子序列是 [2,3,7,101]，因此长度为 4 。

解题思路

这是一个经典的动态规划问题，我们可以定义dp[i]表示以第i个元素结尾的最长递增子序列的长度。

状态转移方程：dp[i] = max(dp[j] + 1)，其中j < i且nums[j] < nums[i]

边界条件：dp[i] = 1，表示每个元素自身是一个长度为1的子序列

public int lengthOfLIS(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    int n = nums.length;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);
    int maxLength = 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);
            }
        }
        maxLength = Math.max(maxLength, dp[i]);
    }
    return maxLength;
}

时间复杂度：O(n²)，其中n是数组的长度。需要填充n大小的dp数组，每个位置需要比较n次。 空间复杂度：O(n)，需要一个大小为n的dp数组。

优化版本（贪心+二分查找）：

我们可以维护一个数组tails，其中tails[i]表示长度为i+1的递增子序列的末尾元素的最小值。

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

时间复杂度：O(n log n)，其中n是数组的长度。对于每个元素，我们需要进行一次二分查找，时间复杂度为O(log n)。 空间复杂度：O(n)，需要一个大小为n的tails数组。

三、动态规划进阶问题

3.1 0-1背包问题（LeetCode 416）

题目描述：给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例：输入：[1,5,11,5] 输出：true 解释：数组可以分割成 [1, 5, 5] 和 [11]。

解题思路

这是一个典型的0-1背包问题，我们可以将其转化为：是否可以从数组中选择一些元素，使得它们的和等于数组总和的一半。

状态定义：dp[i][j]表示前i个元素中是否可以选出一些元素，使得它们的和为j

状态转移方程：dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]]

边界条件：dp[0][0] = true，表示前0个元素可以选出和为0的子集

public boolean canPartition(int[] nums) {
    if (nums == null || nums.length == 0) {
        return false;
    }
    int sum = 0;
    for (int num : nums) {
        sum += num;
    }
    // 如果总和为奇数，无法分成两个和相等的子集
    if (sum % 2 != 0) {
        return false;
    }
    int target = sum / 2;
    int n = nums.length;
    boolean[][] dp = new boolean[n + 1][target + 1];
    dp[0][0] = true;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= target; j++) {
            if (j < nums[i - 1]) {
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
            }
        }
    }
    return dp[n][target];
}

空间优化版本：

由于每次计算dp[i][j]只需要用到dp[i-1][j]和dp[i-1][j-nums[i-1]]，我们可以使用一维数组来优化空间。

public boolean canPartition(int[] nums) {
    if (nums == null || nums.length == 0) {
        return false;
    }
    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];
}

时间复杂度：O(n * target)，其中n是数组的长度，target是数组总和的一半。 空间复杂度：O(target)，需要一个大小为target+1的dp数组。

3.2 完全背包问题（LeetCode 322的变种）

题目描述：给定不同面额的硬币和一个总金额。假设每一种面额的硬币有无限个。计算可以凑成总金额的组合数。

示例：输入：amount = 5, coins = [1, 2, 5] 输出：4 解释：有四种方式可以凑成总金额： 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1

解题思路

这是一个典型的完全背包问题，我们可以定义dp[i]表示凑成总金额i的组合数。

状态转移方程：dp[i] += dp[i-coin]，其中coin是硬币的面额

边界条件：dp[0] = 1，表示凑成总金额0的方式只有1种（不选任何硬币）

public int change(int amount, int[] coins) {
    if (amount == 0) {
        return 1;
    }
    if (coins == null || coins.length == 0) {
        return 0;
    }
    int[] dp = new int[amount + 1];
    dp[0] = 1;
    // 注意这里的遍历顺序，先遍历硬币，再遍历金额
    // 这样可以保证每个硬币只使用一次
    for (int coin : coins) {
        for (int i = coin; i <= amount; i++) {
            dp[i] += dp[i - coin];
        }
    }
    return dp[amount];
}

时间复杂度：O(amount * n)，其中n是硬币的种类数。 空间复杂度：O(amount)，需要一个大小为amount+1的dp数组。

3.3 编辑距离（LeetCode 72）

题目描述：给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数。你可以对一个单词进行如下三种操作：

插入一个字符
删除一个字符
替换一个字符

示例：输入：word1 = “horse”, word2 = “ros” 输出：3 解释： horse -> rorse (将 ‘h’ 替换为 ‘r’) rorse -> rose (删除 ‘r’) rose -> ros (删除 ‘e’)

解题思路

这是一个经典的编辑距离问题，我们可以定义dp[i][j]表示将word1的前i个字符转换成word2的前j个字符所需的最少操作数。

状态转移方程：

如果word1[i-1] == word2[j-1]，则dp[i][j] = dp[i-1][j-1]
否则，dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
- dp[i-1][j]表示删除word1的第i个字符
- dp[i][j-1]表示在word1的第i个字符后插入一个字符
- dp[i-1][j-1]表示将word1的第i个字符替换为word2的第j个字符

边界条件：

dp[i][0] = i，表示将word1的前i个字符转换成空字符串需要删除i个字符
dp[0][j] = j，表示将空字符串转换成word2的前j个字符需要插入j个字符

public int minDistance(String word1, String word2) {
    if (word1 == null || word2 == null) {
        return 0;
    }
    int m = word1.length();
    int 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(
                    Math.min(dp[i - 1][j], dp[i][j - 1]), // 删除和插入
                    dp[i - 1][j - 1]                     // 替换
                ) + 1;
            }
        }
    }
    return dp[m][n];
}

时间复杂度：O(mn)，其中m和n分别是两个字符串的长度。 空间复杂度：O(mn)，需要一个m×n的dp数组。

3.4 打家劫舍（LeetCode 198）

题目描述：你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。

示例：输入：[1,2,3,1] 输出：4 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。

解题思路

这是一个典型的动态规划问题，我们可以定义dp[i]表示偷窃到第i个房屋时能够获得的最高金额。

状态转移方程：dp[i] = max(dp[i-1], dp[i-2] + nums[i])

边界条件：

dp[0] = nums[0]，表示偷窃第一个房屋的金额
dp[1] = max(nums[0], nums[1])，表示偷窃前两个房屋中的最大值

public int rob(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    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];
}

空间优化版本：

public int rob(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    int n = nums.length;
    if (n == 1) {
        return nums[0];
    }
    int prev = nums[0];
    int curr = Math.max(nums[0], nums[1]);
    for (int i = 2; i < n; i++) {
        int next = Math.max(curr, prev + nums[i]);
        prev = curr;
        curr = next;
    }
    return curr;
}

时间复杂度：O(n)，其中n是数组的长度。 空间复杂度：O(1)，只使用了常数级别的额外空间。

3.5 最长回文子串（LeetCode 5）

题目描述：给你一个字符串 s，找到 s 中最长的回文子串。

示例：输入：s = “babad” 输出：“bab” 或 “aba”

解题思路

这道题可以使用动态规划或中心扩展法来解决。这里介绍动态规划法。

状态定义：dp[i][j]表示字符串s的子串s[i…j]是否是回文串

状态转移方程：dp[i][j] = (s[i] == s[j]) && dp[i+1][j-1]

边界条件：

当j == i时，dp[i][j] = true，表示单个字符是回文串
当j == i+1时，dp[i][j] = (s[i] == s[j])，表示两个相同的字符是回文串

public String longestPalindrome(String s) {
    if (s == null || s.isEmpty()) {
        return "";
    }
    int n = s.length();
    boolean[][] dp = new boolean[n][n];
    int start = 0;
    int maxLength = 1;
    // 初始化单个字符的情况
    for (int i = 0; i < n; i++) {
        dp[i][i] = true;
    }
    // 初始化两个字符的情况
    for (int i = 0; i < n - 1; i++) {
        if (s.charAt(i) == s.charAt(i + 1)) {
            dp[i][i + 1] = true;
            start = i;
            maxLength = 2;
        }
    }
    // 填充dp数组，长度从3开始
    for (int len = 3; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            if (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]) {
                dp[i][j] = true;
                start = i;
                maxLength = len;
            }
        }
    }
    return s.substring(start, start + maxLength);
}

时间复杂度：O(n²)，其中n是字符串的长度。需要填充n×n的dp数组。 空间复杂度：O(n²)，需要一个n×n的dp数组。

四、动态规划高级应用

4.1 股票买卖问题系列

股票买卖问题是动态规划的一个重要应用场景，LeetCode上有一系列相关的题目。这里我们以其中的几道经典题目为例进行解析。

4.1.1 买卖股票的最佳时机（LeetCode 121）

题目描述：给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。

示例：输入：[7,1,5,3,6,4] 输出：5 解释：在第 2 天（价格 = 1）的时候买入，在第 5 天（价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

解题思路

这道题可以使用动态规划或一次遍历的方法来解决。这里介绍一次遍历的方法。

public int maxProfit(int[] prices) {
    if (prices == null || prices.length <= 1) {
        return 0;
    }
    int minPrice = prices[0];
    int maxProfit = 0;
    for (int i = 1; i < prices.length; i++) {
        if (prices[i] < minPrice) {
            minPrice = prices[i];
        } else {
            maxProfit = Math.max(maxProfit, prices[i] - minPrice);
        }
    }
    return maxProfit;
}

时间复杂度：O(n)，其中n是数组的长度。只需要遍历一次数组。 空间复杂度：O(1)，只使用了常数级别的额外空间。

4.1.2 买卖股票的最佳时机 II（LeetCode 122）

题目描述：给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

示例：输入：[7,1,5,3,6,4] 输出：7 解释：在第 2 天（价格 = 1）的时候买入，在第 3 天（价格 = 5）的时候卖出，这笔交易所能获得利润 = 5-1 = 4 。随后，在第 4 天（价格 = 3）的时候买入，在第 5 天（价格 = 6）的时候卖出，这笔交易所能获得利润 = 6-3 = 3 。总利润为 4 + 3 = 7 。

解题思路

这道题可以使用贪心算法或动态规划来解决。这里介绍贪心算法。

public int maxProfit(int[] prices) {
    if (prices == null || prices.length <= 1) {
        return 0;
    }
    int maxProfit = 0;
    for (int i = 1; i < prices.length; i++) {
        // 如果当天价格高于前一天，就进行交易
        if (prices[i] > prices[i - 1]) {
            maxProfit += prices[i] - prices[i - 1];
        }
    }
    return maxProfit;
}

时间复杂度：O(n)，其中n是数组的长度。只需要遍历一次数组。 空间复杂度：O(1)，只使用了常数级别的额外空间。

4.2 矩阵路径问题

4.2.1 最小路径和（LeetCode 64）

题目描述：给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。说明：每次只能向下或者向右移动一步。

示例：输入：grid = [[1,3,1],[1,5,1],[4,2,1]] 输出：7 解释：因为路径 1→3→1→1→1 的总和最小。

解题思路

这是一个典型的二维动态规划问题，我们可以定义dp[i][j]表示从左上角到位置(i,j)的最小路径和。

状态转移方程：dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

边界条件：

dp[0][0] = grid[0][0]
对于第一行，dp[0][j] = dp[0][j-1] + grid[0][j]
对于第一列，dp[i][0] = dp[i-1][0] + grid[i][0]

public int minPathSum(int[][] grid) {
    if (grid == null || grid.length == 0 || grid[0].length == 0) {
        return 0;
    }
    int m = grid.length;
    int n = grid[0].length;
    int[][] dp = new int[m][n];
    dp[0][0] = grid[0][0];
    // 初始化第一行
    for (int j = 1; j < n; j++) {
        dp[0][j] = dp[0][j - 1] + grid[0][j];
    }
    // 初始化第一列
    for (int i = 1; i < m; i++) {
        dp[i][0] = dp[i - 1][0] + grid[i][0];
    }
    // 填充dp数组
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[m - 1][n - 1];
}

时间复杂度：O(mn)，其中m和n分别是网格的行数和列数。 空间复杂度：O(mn)，需要一个m×n的dp数组。

4.2.2 不同路径（LeetCode 62）

题目描述：一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。问总共有多少条不同的路径？

示例：输入：m = 3, n = 7 输出：28

解题思路

这是一个典型的组合数学问题或动态规划问题，我们可以定义dp[i][j]表示从左上角到位置(i,j)的不同路径数。

状态转移方程：dp[i][j] = dp[i-1][j] + dp[i][j-1]

边界条件：

dp[0][0] = 1
对于第一行，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;
    }
    // 填充dp数组
    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];
}

时间复杂度：O(mn)，其中m和n分别是网格的行数和列数。 空间复杂度：O(mn)，需要一个m×n的dp数组。

4.3 字符串相关的动态规划问题

4.3.1 最长公共子序列（LeetCode 1143）

题目描述：给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回 0 。

示例：输入：text1 = “abcde”, text2 = “ace” 输出：3 解释：最长公共子序列是 “ace”，它的长度为 3。

解题思路

这是一个经典的二维动态规划问题，我们可以定义dp[i][j]表示text1的前i个字符和text2的前j个字符的最长公共子序列长度。

状态转移方程：

如果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])

边界条件：dp[i][0] = 0，dp[0][j] = 0

public int longestCommonSubsequence(String text1, String text2) {
    if (text1 == null || text2 == null || text1.isEmpty() || text2.isEmpty()) {
        return 0;
    }
    int m = text1.length();
    int 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];
}

时间复杂度：O(mn)，其中m和n分别是两个字符串的长度。 空间复杂度：O(mn)，需要一个m×n的dp数组。

五、动态规划实战技巧总结

5.1 状态设计技巧

根据问题要求设计状态：明确dp数组的含义，通常是“到某个位置/状态时的最优解”
状态维度的选择：根据问题的复杂度选择一维、二维或更高维的状态
状态压缩：对于某些问题，可以通过观察状态转移方程，将高维状态压缩为低维状态

5.2 状态转移方程的推导技巧

分析最后一步：思考问题的最后一步操作是什么，以及如何从子问题的解得到原问题的解
考虑所有可能的转移方式：确保状态转移方程考虑了所有可能的情况
利用数学归纳法：假设对于所有小于i的情况都已经求解，那么如何求解i的情况

5.3 初始化技巧

根据状态定义初始化：根据dp数组的含义设置初始值
处理边界情况：对于无法通过状态转移方程计算的边界情况，需要单独处理
使用哨兵值：为了简化计算，可以在数组的开头或结尾添加哨兵值

5.4 遍历顺序的确定

根据状态转移方程确定：确保在计算dp[i][j]时，所需的dp[i-1][j]、dp[i][j-1]等已经被计算
正向遍历和反向遍历：对于某些问题（如0-1背包），需要注意遍历的方向以避免重复计算
按维度遍历：对于多维dp数组，需要确定遍历的顺序（按行优先或按列优先）

5.5 常见错误与注意事项

状态定义不清晰：确保dp数组的含义明确，避免在推导状态转移方程时出现错误
边界条件处理不当：遗漏或错误处理边界情况，导致结果不正确
状态转移方程推导错误：没有考虑所有可能的转移方式，或推导过程中出现逻辑错误
数组越界：在访问数组元素时，需要确保索引在有效范围内
数据类型溢出：对于较大的结果，需要使用合适的数据类型（如long）避免溢出

六、面试高频动态规划问题

6.1 跳跃游戏（LeetCode 55）

题目描述：给定一个非负整数数组 nums ，你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。

示例：输入：nums = [2,3,1,1,4] 输出：true 解释：可以先跳 1 步，从位置 0 到达位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。

解题思路

这道题可以使用贪心算法或动态规划来解决。这里介绍动态规划法。

public boolean canJump(int[] nums) {
    if (nums == null || nums.length == 0) {
        return false;
    }
    int n = nums.length;
    boolean[] dp = new boolean[n];
    dp[0] = true;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j] && j + nums[j] >= i) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[n - 1];
}

时间复杂度：O(n²)，其中n是数组的长度。 空间复杂度：O(n)，需要一个大小为n的dp数组。

贪心算法优化版本：

public boolean canJump(int[] nums) {
    if (nums == null || nums.length == 0) {
        return false;
    }
    int maxReach = 0;
    for (int i = 0; i < nums.length; i++) {
        if (i > maxReach) {
            return false;
        }
        maxReach = Math.max(maxReach, i + nums[i]);
        if (maxReach >= nums.length - 1) {
            return true;
        }
    }
    return true;
}

时间复杂度：O(n)，其中n是数组的长度。 空间复杂度：O(1)，只使用了常数级别的额外空间。

6.2 乘积最大子数组（LeetCode 152）

题目描述：给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

示例：输入：[2,3,-2,4] 输出：6 解释：子数组 [2,3] 有最大乘积 6。

解题思路

这道题需要同时跟踪最大乘积和最小乘积，因为负负得正的特性。

public int maxProduct(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    int n = nums.length;
    int maxProduct = nums[0];
    int currMax = nums[0];
    int currMin = nums[0];
    for (int i = 1; i < n; i++) {
        int temp = currMax;
        // 当前的最大值可能来自于当前值、当前值乘以之前的最大值、当前值乘以之前的最小值
        currMax = Math.max(nums[i], Math.max(nums[i] * currMax, nums[i] * currMin));
        // 当前的最小值可能来自于当前值、当前值乘以之前的最大值、当前值乘以之前的最小值
        currMin = Math.min(nums[i], Math.min(nums[i] * temp, nums[i] * currMin));
        maxProduct = Math.max(maxProduct, currMax);
    }
    return maxProduct;
}

时间复杂度：O(n)，其中n是数组的长度。 空间复杂度：O(1)，只使用了常数级别的额外空间。

6.3 分割等和子集（LeetCode 416）

题目描述：给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例：输入：[1,5,11,5] 输出：true 解释：数组可以分割成 [1, 5, 5] 和 [11]。

解题思路

这道题可以转化为0-1背包问题，详见3.1节。

6.4 打家劫舍 III（LeetCode 337）

题目描述：在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

示例：输入：[3,2,3,null,3,null,1] 输出：7 解释：小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.

解题思路

这道题可以使用动态规划结合树形递归或后序遍历来解决。

public int rob(TreeNode root) {
    int[] result = robHelper(root);
    // result[0]表示不偷当前节点的最大金额，result[1]表示偷当前节点的最大金额
    return Math.max(result[0], result[1]);
}

private int[] robHelper(TreeNode root) {
    if (root == null) {
        return new int[]{0, 0};
    }
    int[] left = robHelper(root.left);
    int[] right = robHelper(root.right);
    // 不偷当前节点，可以选择偷或不偷子节点
    int notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
    // 偷当前节点，不能偷子节点
    int rob = root.val + left[0] + right[0];
    return new int[]{notRob, rob};
}

时间复杂度：O(n)，其中n是树中的节点数。 空间复杂度：O(h)，其中h是树的高度，最坏情况下为O(n)。

七、动态规划思维训练与扩展

7.1 多维动态规划

多维动态规划是一维动态规划的扩展，常见的有二维和三维动态规划。在处理多维动态规划问题时，需要注意以下几点：

状态定义：明确多维dp数组的每个维度代表什么
状态转移方程：分析多维状态之间的转移关系
空间优化：对于某些问题，可以通过观察状态转移方程，将多维状态压缩为低维状态

7.2 状态压缩动态规划

状态压缩动态规划是一种将状态用二进制表示的动态规划方法，常用于解决子集选择问题。在状态压缩动态规划中，通常使用一个整数来表示一个子集，每一位表示一个元素是否被选中。

7.3 数位动态规划

数位动态规划是一种用于解决与数字相关的计数问题的动态规划方法，通常用于统计满足某些条件的数的个数。在数位动态规划中，通常将数字拆分成各个位，然后逐位处理。

7.4 动态规划的优化技巧

空间优化：对于只依赖于前几个状态的问题，可以使用滚动数组或变量来优化空间
时间优化：通过预处理或剪枝来优化时间复杂度
状态优化：合并或简化状态，减少状态的数量

八、总结与展望

动态规划是一种解决复杂问题的强大工具，它通过将原问题分解为相对简单的子问题，利用子问题的解来构建原问题的解。动态规划在算法面试中占据着重要的地位，掌握好动态规划对于提高算法能力至关重要。

通过本文的学习，我们了解了动态规划的基本概念、核心思想和解题步骤，掌握了常见的动态规划问题类型和解法，并通过具体的LeetCode题目解析，深入理解了动态规划的实际应用。

在解决动态规划问题时，我们需要注意以下几点：

正确定义状态：明确dp数组的含义，这是解决动态规划问题的关键
推导状态转移方程：分析状态之间的转移关系，确保考虑了所有可能的情况
处理边界条件：正确初始化dp数组，处理无法通过状态转移方程计算的边界情况
确定遍历顺序：根据状态转移方程确定遍历的顺序，确保在计算当前状态时，所需的状态已经被计算
优化空间和时间复杂度：在保证正确性的前提下，尽量优化算法的空间和时间复杂度

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-09-21，如有侵权请联系 cloudcommunity@tencent.com 删除

数组

leetcode

动态规划

基础

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！