力扣热题 100：动态规划专题经典题解析

系列文章目录

力扣热题 100：哈希专题三道题详细解析(JAVA)
力扣热题 100：双指针专题四道题详细解析(JAVA)
力扣热题 100：滑动窗口专题两道题详细解析（JAVA）
力扣热题 100：子串专题三道题详细解析(JAVA)
力扣热题 100：普通数组专题五道题详细解析(JAVA)
力扣热题 100：矩阵专题四道题详细解析（JAVA）
力扣热题 100：链表专题经典题解析(前7道)
力扣热题 100：链表专题经典题解析（后7道）
力扣热题 100：二叉树专题经典题解析（前8道）
力扣热题 100：二叉树专题进阶题解析（后7道）
力扣热题 100：图论专题经典题解析
力扣热题 100：回溯专题经典题解析
力扣热题 100：二分查找专题经典题解析
力扣热题 100：栈专题经典题解析
力扣热题 100：堆专题经典题解析
力扣热题 100：贪心算法专题经典题解析
力扣热题 100：动态规划专题经典题解析
力扣热题 100：多维动态规划专题经典题解析
力扣热题 100：技巧专题经典题解析

在力扣（LeetCode）平台上，动态规划相关的题目是算法面试和练习中的重要部分。今天，我们就来详细解析动态规划专题中的几道经典题目，帮助大家更好地理解解题思路和技巧。

一、爬楼梯（题目 70）

1. 题目描述

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

2. 示例

示例 1：

输入：n = 2

输出：2

解释：有两种方法：1 阶 + 1 阶 或 2 阶。

示例 2：

输入：n = 3

输出：3

解释：有三种方法：1+1+1, 1+2, 2+1。

3. 解题思路

这道题主要考察动态规划的应用。我们可以使用动态规划来记录到达每个台阶的方法数。具体步骤如下：

1. 定义一个数组 dp，其中 dp[i] 表示到达第 i 阶的方法数。
2. 初始化 dp[0] = 1（到达第 0 阶的方法数为 1，即不动）和 dp[1] = 1（到达第 1 阶的方法数为 1，即爬 1 阶）。
3. 对于每个台阶 i，其方法数等于到达前一阶和前两阶的方法数之和，即 dp[i] = dp[i-1] + dp[i-2]。

4. 代码实现（Java）

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

5. 复杂度分析

• 时间复杂度 ：O(n)，其中 n 是台阶数。我们需要遍历从 2 到 n 的所有台阶。
• 空间复杂度 ：O(n)，需要使用数组存储每个台阶的方法数。可以优化为 O(1) 空间，只保留前两个状态。

二、杨辉三角（题目 118）

1. 题目描述

给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。

2. 示例

示例 1：

输入：numRows = 5

输出：[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]

3. 解题思路

这道题主要考察动态规划的应用。我们可以使用动态规划来生成杨辉三角的每一行。具体步骤如下：

1. 初始化一个二维列表 result，用于存储杨辉三角的每一行。
2. 对于每一行 i，初始化一个长度为 i+1 的列表，并将首尾元素设为 1。
3. 对于中间的元素，其值等于上一行对应位置的元素和前一个元素之和。

4. 代码实现（Java）

import java.util.ArrayList;
import java.util.List;public class Solution {public List<List<Integer>> generate(int numRows) {List<List<Integer>> result = new ArrayList<>();for (int i = 0; i < numRows; i++) {List<Integer> row = new ArrayList<>();for (int j = 0; j <= i; j++) {if (j == 0 || j == i) {row.add(1);} else {row.add(result.get(i - 1).get(j - 1) + result.get(i - 1).get(j));}}result.add(row);}return result;}
}

5. 复杂度分析

• 时间复杂度 ：O(numRows^2)，需要生成每一行的每个元素。
• 空间复杂度 ：O(numRows^2)，需要存储杨辉三角的所有元素。

三、打家劫舍（题目 198）

1. 题目描述

给定一个整数数组 nums 表示每个房子中的金额，相邻的房子不能同时被抢劫。求能抢劫到的最大金额。

2. 示例

示例 1：

输入：nums = [1, 2, 3, 1]

输出：4

解释：抢劫第 2 个和第 3 个房子，金额为 2 + 3 = 5。

3. 解题思路

这道题主要考察动态规划的应用。我们可以使用动态规划来记录每个房子能抢劫到的最大金额。具体步骤如下：

1. 定义一个数组 dp，其中 dp[i] 表示前 i 个房子能抢劫到的最大金额。
2. 初始化 dp[0] = nums[0] 和 dp[1] = Math.max(nums[0], nums[1])。
3. 对于每个房子 i，其最大金额等于 Math.max(dp[i-1], dp[i-2] + nums[i])。

4. 代码实现（Java）

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

5. 复杂度分析

• 时间复杂度 ：O(n)，其中 n 是房子的数量。需要遍历每个房子一次。
• 空间复杂度 ：O(n)，需要使用数组存储每个房子的最大金额。可以优化为 O(1) 空间，只保留前两个状态。

四、完全平方数（题目 279）

1. 题目描述

给定一个正整数 n，找到最少数量的完全平方数的和等于 n。

2. 示例

示例 1：

输入：n = 12

输出：3

解释：4 + 4 + 4 = 12。

3. 解题思路

这道题主要考察动态规划的应用。我们可以使用动态规划来记录每个数的最少完全平方数数量。具体步骤如下：

1. 定义一个数组 dp，其中 dp[i] 表示和为 i 的最少完全平方数数量。
2. 初始化 dp[0] = 0。
3. 对于每个数 i，遍历所有可能的完全平方数 j，更新 dp[i] = Math.min(dp[i], dp[i - j] + 1)。

4. 代码实现（Java）

public class Solution {public int numSquares(int n) {int[] dp = new int[n + 1];Arrays.fill(dp, Integer.MAX_VALUE);dp[0] = 0;for (int i = 1; i <= n; i++) {for (int j = 1; j * j <= i; j++) {dp[i] = Math.min(dp[i], dp[i - j * j] + 1);}}return dp[n];}
}

5. 复杂度分析

• 时间复杂度 ：O(n * sqrt(n))，需要遍历每个数和其可能的完全平方数。
• 空间复杂度 ：O(n)，需要使用数组存储每个数的最少数量。

五、零钱兑换（题目 322）

1. 题目描述

给定不同面额的硬币和一个总金额，求凑成总金额所需的最少硬币数。如果无法凑成，返回 -1。

2. 示例

示例 1：

输入：coins = [1, 2, 5], amount = 11

输出：3

解释：5 + 5 + 1 = 11。

3. 解题思路

这道题主要考察动态规划的应用。我们可以使用动态规划来记录每个金额的最少硬币数。具体步骤如下：

1. 定义一个数组 dp，其中 dp[i] 表示金额为 i 时的最少硬币数。
2. 初始化 dp[0] = 0，其余为 Integer.MAX_VALUE。
3. 对于每个金额 i，遍历所有硬币，更新 dp[i] = Math.min(dp[i], dp[i - coin] + 1)。

4. 代码实现（Java）

public class Solution {public int coinChange(int[] coins, int amount) {int[] dp = new int[amount + 1];Arrays.fill(dp, Integer.MAX_VALUE);dp[0] = 0;for (int i = 1; i <= amount; i++) {for (int coin : coins) {if (coin <= i && dp[i - coin] != Integer.MAX_VALUE) {dp[i] = Math.min(dp[i], dp[i - coin] + 1);}}}return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];}
}

5. 复杂度分析

• 时间复杂度 ：O(amount * coins.length)，需要遍历每个金额和每个硬币。
• 空间复杂度 ：O(amount)，需要使用数组存储每个金额的最少硬币数。

六、单词拆分（题目 139）

1. 题目描述

给定一个字符串 s 和一个单词集合 wordDict，判断 s 是否可以被拆分成一个或多个在单词集合中出现的单词。

2. 示例

示例 1：

输入：s = "leetcode", wordDict = ["leet", "code"]

输出：true

解释："leetcode" 可以被拆分成 "leet code"。

3. 解题思路

这道题主要考察动态规划的应用。我们可以使用动态规划来记录字符串的每个位置是否可以被拆分。具体步骤如下：

1. 定义一个数组 dp，其中 dp[i] 表示字符串的前 i 个字符是否可以被拆分。
2. 初始化 dp[0] = true（空字符串可以被拆分）。
3. 对于每个位置 i，遍历所有可能的单词长度，检查是否可以拆分。

4. 代码实现（Java）

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

5. 复杂度分析

• 时间复杂度 ：O(n^2)，其中 n 是字符串的长度。需要遍历每个位置和每个可能的单词长度。
• 空间复杂度 ：O(n)，需要使用数组存储每个位置的拆分状态。

七、最长递增子序列（题目 300）

1. 题目描述

给定一个整数数组 nums，找到最长递增子序列的长度。

2. 示例

示例 1：

输入：nums = [10, 9, 2, 5, 3, 7, 101, 18]

输出：4

解释：最长递增子序列是 [2, 3, 7, 101]。

3. 解题思路

这道题主要考察动态规划的应用。我们可以使用动态规划来记录每个位置的最长递增子序列长度。具体步骤如下：

1. 定义一个数组 dp，其中 dp[i] 表示以 nums[i] 结尾的最长递增子序列长度。
2. 初始化 dp 数组为全 1。
3. 对于每个位置 i，遍历其前面的所有位置 j，如果 nums[i] > nums[j]，则 dp[i] = Math.max(dp[i], dp[j] + 1)。

4. 代码实现（Java）

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

5. 复杂度分析

• 时间复杂度 ：O(n^2)，其中 n 是数组的长度。需要遍历每个位置和其前面的所有位置。
• 空间复杂度 ：O(n)，需要使用数组存储每个位置的最长递增子序列长度。可以优化为 O(n log n) 时间复杂度，使用二分查找。

八、乘积最大子数组（题目 152）

1. 题目描述

给定一个整数数组 nums，找到一个子数组，使得该子数组的乘积最大。返回这个最大乘积。

2. 示例

示例 1：

输入：nums = [2, 3, -2, 4]

输出：6

解释：子数组 [2, 3] 的乘积为 6。

3. 解题思路

这道题主要考察动态规划的应用。由于乘积可能为负数，我们需要同时记录最大值和最小值。具体步骤如下：

1. 定义两个数组 maxDp 和 minDp，分别记录以当前元素结尾的最大乘积和最小乘积。
2. 初始化 maxDp[0] = nums[0] 和 minDp[0] = nums[0]。
3. 对于每个元素 i，计算 maxDp[i] = Math.max(nums[i], Math.max(maxDp[i-1] * nums[i], minDp[i-1] * nums[i])) 和 minDp[i] = Math.min(nums[i], Math.min(maxDp[i-1] * nums[i], minDp[i-1] * nums[i]))。

4. 代码实现（Java）

public class Solution {public int maxProduct(int[] nums) {if (nums.length == 0) return 0;int[] maxDp = new int[nums.length];int[] minDp = new int[nums.length];maxDp[0] = nums[0];minDp[0] = nums[0];int max = nums[0];for (int i = 1; i < nums.length; i++) {maxDp[i] = Math.max(nums[i], Math.max(maxDp[i - 1] * nums[i], minDp[i - 1] * nums[i]));minDp[i] = Math.min(nums[i], Math.min(maxDp[i - 1] * nums[i], minDp[i - 1] * nums[i]));max = Math.max(max, maxDp[i]);}return max;}
}

5. 复杂度分析

• 时间复杂度 ：O(n)，其中 n 是数组的长度。需要遍历每个元素一次。
• 空间复杂度 ：O(n)，需要使用两个数组存储最大值和最小值。可以优化为 O(1) 空间，只保留前一个状态。

九、分割等和子集（题目 416）

1. 题目描述

给定一个非空整数数组 nums，判断是否可以将其划分为两个子集，使得两个子集的元素和相等。

2. 示例

示例 1：

输入：nums = [1, 5, 11, 5]

输出：true

解释：可以划分为 [1, 5, 5] 和 [11]。

3. 解题思路

这道题主要考察动态规划的应用。我们可以将问题转化为背包问题，判断是否存在一个子集的和等于总和的一半。具体步骤如下：

1. 计算数组的总和 sum，如果 sum 是奇数，则无法分割。
2. 定义一个数组 dp，其中 dp[i] 表示是否可以达到和为 i 的子集。
3. 初始化 dp[0] = true。
4. 遍历每个数，更新 dp 数组。

4. 代码实现（Java）

public class Solution {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 i = target; i >= num; i--) {dp[i] = dp[i] || dp[i - num];}}return dp[target];}
}

5. 复杂度分析

• 时间复杂度 ：O(n * target)，其中 n 是数组的长度，target 是总和的一半。
• 空间复杂度 ：O(target)，需要使用数组存储是否可以达到每个和。

十、最长有效括号（题目 32）

1. 题目描述

给定一个只包含 '(' 和 ')' 的字符串，找到最长的有效括号子串的长度。

2. 示例

示例 1：

输入：s = "(()"

输出：2

解释：最长的有效括号子串是 "()"

3. 解题思路

这道题主要考察动态规划的应用。我们可以使用动态规划来记录每个位置的最长有效括号长度。具体步骤如下：

1. 定义一个数组 dp，其中 dp[i] 表示以 i 结尾的最长有效括号子串的长度。
2. 初始化 dp 数组为全 0。
3. 遍历字符串，当遇到 ')' 时，检查前面的字符是否为 '(' 或者前面的子串是否有效，更新 dp[i]。

4. 代码实现（Java）

public class Solution {public int longestValidParentheses(String s) {int maxLen = 0;int[] dp = new int[s.length()];for (int i = 1; i < s.length(); i++) {if (s.charAt(i) == ')') {if (s.charAt(i - 1) == '(') {dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;} else if (i - dp[i - 1] - 1 >= 0 && s.charAt(i - dp[i - 1] - 1) == '(') {dp[i] = dp[i - 1] + 2 + (i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] : 0);}maxLen = Math.max(maxLen, dp[i]);}}return maxLen;}
}

5. 复杂度分析

• 时间复杂度 ：O(n)，其中 n 是字符串的长度。需要遍历每个字符一次。
• 空间复杂度 ：O(n)，需要使用数组存储每个位置的最长有效括号长度。

以上就是力扣热题 100 中与动态规划相关的经典题目的详细解析，希望对大家有所帮助。在实际刷题过程中，建议大家多动手实践，理解解题思路的本质，这样才能更好地应对各种算法问题。