力扣Hot100系列20（Java）——[动态规划]总结（下）( 单词拆分，最大递增子序列，乘积最大子数组 ，分割等和子集，最长有效括号)

文章目录

• 前言
• 一、单词拆分
• • 1.题目
  • 2.代码
  • 3.例子
• 二、最大递增子序列
• • 1.题目
  • 2.代码
  • 3.例子
• 三、乘积最大子数组
• • 1.题目
  • 2.代码
  • 3.例子
• 四、分割等和子集
• • 1.题目
  • 2.代码
  • 3.例子
• 五、最长有效括号
• • 1.题目
  • 2.代码
  • 3.例子

前言

本文记录力扣Hot100里面关于动态规划的五道题，包括常见解法和一些关键步骤理解，也有例子便于大家理解

一、单词拆分

1.题目

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。 注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例 1： 输入: s = “leetcode”, wordDict = [“leet”, “code”] 输出: true 解释: 返回 true 因为 “leetcode” 可以由 “leet” 和 “code” 拼接成。

示例 2： 输入: s = “applepenapple”, wordDict = [“apple”, “pen”] 输出: true 解释: 返回 true 因为 “applepenapple” 可以由 “apple” “pen” “apple” 拼接成。 注意，你可以重复使用字典中的单词。

示例 3： 输入: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”] 输出: false

提示：

• 1 <= s.length <= 300
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 20
• s 和 wordDict[i] 仅由小写英文字母组成
• wordDict 中的所有字符串 互不相同

2.代码

public class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
// 1. 把单词列表转成HashSet：目的是快速判断某个子串是否在字典里（HashSet的contains方法时间复杂度O(1)）
Set<String> wordDictSet = new HashSet(wordDict);

// 2. 定义dp数组：dp[i]表示s的前i个字符（s[0..i-1]）能否被拆分，长度为s.length()+1（覆盖0~s.length()）
boolean[] dp = new boolean[s.length() + 1];

// 3. 边界条件：dp[0] = true → 空字符串（前0个字符）可以被拆分（作为拆分的“起点”）
dp[0] = true;

// 4. 外层循环：遍历字符串的所有长度，从1到s.length()（判断前1个、前2个…前n个字符能否拆分）
for (int i = 1; i <= s.length(); i++) {
// 5. 内层循环：遍历所有可能的拆分点j（把前i个字符拆成“前j个字符”+“j到i的子串”）
for (int j = 0; j < i; j++) {
// 6. 判断条件：
// – dp[j] = true → 前j个字符能被拆分（拆分的“前半段有效”）
// – wordDictSet.contains(s.substring(j, i)) → j到i的子串在字典里（拆分的“后半段有效”）
if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
// 7. 只要找到一个有效的拆分点，就说明前i个字符能拆分，标记为true并跳出内层循环（不用再找其他拆分点）
dp[i] = true;
break;
}
}
}

// 8. 返回整个字符串（前s.length()个字符）能否拆分的结果
return dp[s.length()];
}
}

3.例子

输入：

• 字符串 s = "leetcode"
• 单词字典 wordDict = ["leet", "code"]

预期输出：true（因为 “leetcode” 可以拆分成 “leet” + “code”）

1. 初始化准备

// 把字典转成HashSet，方便快速查询
Set<String> wordDictSet = new HashSet<>(Arrays.asList("leet", "code"));
// 定义dp数组，长度为 8 + 1 = 9（"leetcode"长度为8）
boolean[] dp = new boolean[9];
// 边界条件：空字符串可以被拆分
dp[0] = true;

此时 dp = [true, false, false, false, false, false, false, false, false]

2. 外层循环（i 从 1 到 8）

步骤 1：i = 1（判断前1个字符 “l” 能否拆分） 内层 j 从 0 到 0：

• j=0：dp[0] = true，但子串 s[0,1] = "l" 不在字典中 → dp[1] 仍为 false

步骤 2：i = 2（判断前2个字符 “le” 能否拆分） 内层 j 从 0 到 1：

• j=0：子串 “le” 不在字典 → 不满足
• j=1：dp[1] = false → 不满足 → dp[2] = false

步骤 3：i = 3（判断前3个字符 “lee” 能否拆分） 内层 j 从 0 到 2：所有 j 对应的子串（“lee”、“ee”、“e”）都不在字典 → dp[3] = false

步骤 4：i = 4（判断前4个字符 “leet” 能否拆分） 内层 j 从 0 到 3：

• j=0：dp[0] = true，子串 s[0,4] = "leet" 在字典中 → 满足条件！ → 标记 dp[4] = true，跳出内层循环 此时 dp[4] = true，其余仍为 false。

步骤 5：i = 5（判断前5个字符 “leetc” 能否拆分） 内层 j 从 0 到 4：

• j=0：子串 “leetc” 不在字典
• j=1：dp[1] = false
• j=2：dp[2] = false
• j=3：dp[3] = false
• j=4：dp[4] = true，但子串 s[4,5] = "c" 不在字典 → 不满足 → dp[5] = false

步骤 6：i = 6（判断前6个字符 “leetco” 能否拆分） 内层 j 遍历到 4 时：dp[4] = true，但子串 s[4,6] = "co" 不在字典 → dp[6] = false

步骤 7：i = 7（判断前7个字符 “leetcod” 能否拆分） 内层 j 遍历到 4 时：dp[4] = true，但子串 s[4,7] = "cod" 不在字典 → dp[7] = false

步骤 8：i = 8（判断前8个字符 “leetcode” 能否拆分） 内层 j 从 0 到 7，重点看 j=4：

• j=4：dp[4] = true（前4个字符"leet"能拆分），子串 s[4,8] = "code" 在字典中 → 满足条件！ → 标记 dp[8] = true，跳出内层循环

3. 最终返回 返回 dp[8]，结果为 true，符合预期。

二、最大递增子序列

1.题目

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。 子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

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

示例 2： 输入：nums = [0,1,0,3,2,3] 输出：4

示例 3： 输入：nums = [7,7,7,7,7,7,7] 输出：1

2.代码

class Solution {
public int lengthOfLIS(int[] nums) {
// 边界条件：空数组直接返回0
if (nums.length == 0) {
return 0;
}
// dp数组：dp[i]表示以nums[i]为最后一个元素的最长递增子序列长度
int[] dp = new int[nums.length];
// 初始化：第一个元素自身构成长度为1的子序列
dp[0] = 1;
// maxans：记录全局最长长度
int maxans = 1;

// 遍历从第二个元素开始（i从1到末尾）
for (int i = 1; i < nums.length; i++) {
// 初始化：每个元素自身至少构成长度为1的子序列
dp[i] = 1;
// 遍历i之前的所有元素j，找能接在后面的子序列
for (int j = 0; j < i; j++) {
// 如果nums[i] > nums[j]，说明可以接在nums[j]的子序列后面
if (nums[i] > nums[j]) {
// 更新dp[i]：取当前值 和 dp[j]+1 的最大值
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
// 更新全局最长长度
maxans = Math.max(maxans, dp[i]);
}
// 返回全局最长长度
return maxans;
}
}

3.例子

输入：nums = [10, 9, 2, 5, 3, 7, 101, 18] 核心规则：dp[i] 表示以 nums[i] 为最后一个元素的最长递增子序列长度，初始值为1；若 nums[i] > nums[j]（j < i），则 dp[i] = max(dp[i], dp[j]+1)；最终结果是所有 dp 值的最大值。

最终结果 所有元素处理完毕后，dp 数组最终为 [1,1,1,2,2,3,4,4]，取其中的最大值4，这就是最长递增子序列的长度。

三、乘积最大子数组

1.题目

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续 子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。 测试用例的答案是一个 32-位 整数。 请注意，一个只包含一个元素的数组的乘积是这个元素的值。

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

示例 2: 输入: nums = [-2,0,-1] 输出: 0 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

提示:

• 1 <= nums.length <= 2 * 10(4)
• -10 <= nums[i] <= 10
• nums 的任何子数组的乘积都 保证 是一个 32-位 整数

2.代码

class Solution {
public int maxProduct(int[] nums) {
// 1. 初始化：maxF表示以当前元素结尾的子数组的最大乘积，minF表示最小乘积
// 用long是为了避免整数溢出（比如大数相乘超出int范围）
long maxF = nums[0], minF = nums[0];
// 2. 初始化答案为第一个元素（至少有一个元素时，最大乘积至少是它自己）
int ans = nums[0];
// 3. 获取数组长度，方便循环
int length = nums.length;

// 4. 从第二个元素开始遍历（i=1）
for (int i = 1; i < length; ++i) {
// 5. 保存上一轮的maxF和minF（因为后续会修改，必须先存）
long mx = maxF, mn = minF;

// 6. 更新当前maxF：有三种可能，取最大的
// – 上一轮最大乘积 * 当前元素（正正/正负）
// – 当前元素自己（重新开始一个子数组）
// – 上一轮最小乘积 * 当前元素（负负得正）
maxF = Math.max(mx * nums[i], Math.max(nums[i], mn * nums[i]));

// 7. 更新当前minF：有三种可能，取最小的
// – 上一轮最小乘积 * 当前元素（负正/负负）
// – 当前元素自己（重新开始一个子数组）
// – 上一轮最大乘积 * 当前元素（正负得负）
minF = Math.min(mn * nums[i], Math.min(nums[i], mx * nums[i]));

// 8. 处理溢出：如果minF小于int的最小值（-2^31），重置为当前元素
// 这是一个额外的溢出保护，避免后续强转int时出错
if(minF < – (1 << 31)){ // 1<<31 是 2^31，- (1<<31) 是int最小值
minF = nums[i];
}

// 9. 更新全局答案：取当前maxF（强转int）和历史ans的最大值
ans = Math.max((int)maxF, ans);
}
// 10. 返回最终的最大乘积
return ans;
}
}

3.例子

输入：nums = [2, -5, -2, -4, 3] 核心目标：找到连续子数组的最大乘积（最终答案是 (-2)*(-4)*3 = 24）

1. 初始化

• maxF = 2（以第一个元素2结尾的最大乘积）
• minF = 2（以第一个元素2结尾的最小乘积）
• ans = 2（全局最大乘积初始为第一个元素）

2. 处理第二个元素（i=1，nums[1]=-5）

• 先保存上一轮的 mx=2、mn=2
• 计算当前 maxF：对比 2*(-5)=-10、-5、2*(-5)=-10，取最大值 -5
• 计算当前 minF：对比 2*(-5)=-10、-5、2*(-5)=-10，取最小值 -10
• 溢出检查：minF=-10 未超出int范围，无需重置
• 更新 ans：对比 (int)-5 和 2，ans 仍为 2
• 此时：maxF=-5，minF=-10，ans=2

3. 处理第三个元素（i=2，nums[2]=-2）

• 保存上一轮的 mx=-5、mn=-10
• 计算当前 maxF： 对比 (-5)*(-2)=10、-2、(-10)*(-2)=20 → 取最大值 20
• 计算当前 minF： 对比 (-5)*(-2)=10、-2、(-10)*(-2)=20 → 取最小值 -2
• 溢出检查：minF=-2 正常
• 更新 ans：对比 20 和 2，ans 更新为 20
• 此时：maxF=20，minF=-2，ans=20

4. 处理第四个元素（i=3，nums[3]=-4）

• 保存上一轮的 mx=20、mn=-2
• 计算当前 maxF： 对比 20*(-4)=-80、-4、(-2)*(-4)=8 → 取最大值 8
• 计算当前 minF： 对比 20*(-4)=-80、-4、(-2)*(-4)=8 → 取最小值 -80
• 溢出检查：minF=-80 正常
• 更新 ans：对比 8 和 20，ans 仍为 20
• 此时：maxF=8，minF=-80，ans=20

5. 处理第五个元素（i=4，nums[4]=3）

• 保存上一轮的 mx=8、mn=-80
• 计算当前 maxF： 对比 8*3=24、3、(-80)*3=-240 → 取最大值 24
• 计算当前 minF： 对比 8*3=24、3、(-80)*3=-240 → 取最小值 -240
• 溢出检查：minF=-240 正常
• 更新 ans：对比 24 和 20，ans 更新为 24
• 此时：maxF=24，minF=-240，ans=24

最终结果 遍历结束，返回 ans=24，和预期的最大子数组乘积（-2*-4*3=24）一致。

四、分割等和子集

1.题目

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

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

示例 2： 输入：nums = [1,2,3,5] 输出：false 解释：数组不能分割成两个元素和相等的子集

2.代码

public boolean canPartition(int[] nums) {
// 获取数组长度
int n = nums.length;
// 边界条件1：数组长度小于2，无法分割成两个子集
if (n < 2) {
return false;
}

// 计算数组总和sum，同时找出数组中的最大值maxNum
int sum = 0, maxNum = 0;
for (int num : nums) {
sum += num;
maxNum = Math.max(maxNum, num);
}

// 边界条件2：总和为奇数，无法分成两个和相等的子集
if (sum % 2 != 0) {
return false;
}

// 目标值：总和的一半（只要能凑出这个值，剩下的元素和也必然等于这个值）
int target = sum / 2;
// 边界条件3：最大值超过目标值，无法凑出（单个元素就超过一半，其他元素加起来也不够）
if (maxNum > target) {
return false;
}

// 动态规划数组：dp[i][j] 表示前i+1个元素（nums[0]~nums[i]）能否凑出和为j
boolean[][] dp = new boolean[n][target + 1];

// 初始化：任何前i+1个元素都能凑出和为0（选空集即可）
for (int i = 0; i < n; i++) {
dp[i][0] = true;
}

// 初始化：只有第一个元素时，能凑出和为nums[0]
dp[0][nums[0]] = true;

// 遍历从第二个元素开始的所有元素
for (int i = 1; i < n; i++) {
int num = nums[i]; // 当前遍历到的元素值
// 遍历所有可能的目标和（从1到target）
for (int j = 1; j <= target; j++) {
if (j >= num) {
// 情况1：j >= 当前元素，有两种选择：
// 1. 不选当前元素：结果继承dp[i-1][j]（前i个元素能否凑出j）
// 2. 选当前元素：结果看dp[i-1][j-num]（前i个元素能否凑出j-num，加上当前num就凑出j）
// 只要其中一种选择可行，dp[i][j]就为true
dp[i][j] = dp[i – 1][j] | dp[i – 1][j – num];
} else {
// 情况2：j < 当前元素，无法选当前元素，直接继承上一轮结果, 因为肯定凑不出j，凑出来的一定大于j
dp[i][j] = dp[i – 1][j];
}
}
}

// 最终结果：前n个元素能否凑出和为target（总和的一半）
return dp[n – 1][target];
}
}

3.例子

以nums = [1,5,11,5]为例

前置处理（边界判断+基础值计算）

动态规划数组初始化 定义4行12列的boolean型dp数组（行对应前i+1个元素，列对应目标和0~11），初始全为false：

遍历第二个元素（i=1，当前元素num=5） 逐个计算目标和j=1到11的dp[1][j]：

• j=1：j<5，直接继承dp[0][1]，dp[1][1]=true；
• j=2-4：j<5，继承dp[0][j]，均为false；
• j=5：j≥5，dp[0][5]（false）或 dp[0][0]（true），结果为true；
• j=6：j≥5，dp[0][6]（false）或 dp[0][1]（true），结果为true；
• j=7-11：j≥5，继承/计算后均为false； 最终dp[1]行true的列：0、1、5、6。

遍历第三个元素（i=2，当前元素num=11） 逐个计算目标和j=1到11的dp[2][j]：

• j=1-6：j<11，直接继承dp[1][j]，即列0、1、5、6为true，其余为false；
• j=7-10：j<11，继承dp[1][j]，均为false；
• j=11：j≥11，dp[1][11]（false）或 dp[1][0]（true），结果为true； 最终dp[2]行true的列：0、1、5、6、11（此时已凑出目标和11）。

遍历第四个元素（i=3，当前元素num=5） 逐个计算目标和j=1到11的dp[3][j]：

• j=1：j<5，继承dp[2][1]=true；
• j=5：j≥5，dp[2][5]（true）或 dp[2][0]（true）=true；
• j=6：j≥5，dp[2][6]（true）或 dp[2][1]（true）=true；
• j=11：j≥5，dp[2][11]（true）或 dp[2][6]（true）=true；
• 其余j按规则计算，不影响核心结果； 最终dp[3]行true的列包含0、1、5、6、11。

最终结果 返回dp[3][11]，值为true，说明该数组可以分割为两个等和子集（[11]和[1,5,5]，和均为11）。

五、最长有效括号

1.题目

给你一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长有效（格式正确且连续）括号 子串 的长度。

左右括号匹配，即每个左括号都有对应的右括号将其闭合的字符串是格式正确的，比如 “(()())”。

示例 1： 输入：s = “(()” 输出：2 解释：最长有效括号子串是 “()”

示例 2： 输入：s = “)()())” 输出：4 解释：最长有效括号子串是 “()()”

示例 3： 输入：s = “” 输出：0

2.代码

class Solution {
public int longestValidParentheses(String s) {
int maxans = 0; // 全局最长有效括号长度
// dp[i]：以s[i]结尾的最长有效括号长度
int[] dp = new int[s.length()];

for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) == ')') { // 仅处理右括号结尾的情况
// 情况1：s[i-1]是'('，形成"()"基础配对
if (s.charAt(i – 1) == '(') {
dp[i] = (i >= 2 ? dp[i – 2] : 0) + 2;
}
// 情况2：s[i-1]是')'，找嵌套匹配的'('
else if (i – dp[i – 1] > 0 && s.charAt(i – dp[i – 1] – 1) == '(') {
dp[i] = dp[i – 1] + ((i – dp[i – 1]) >= 2 ? dp[i – dp[i – 1] – 2] : 0) + 2;
}
maxans = Math.max(maxans, dp[i]); // 更新最大值
}
}
return maxans;
}
}

3.例子

以s = "()(())"为例（索引0到5）

前置初始化

• 字符串：s[0]='(', s[1]=')', s[2]='(', s[3]='(', s[4]=')', s[5]=')'
• maxans 初始为0，dp 数组长度6，初始全为0（dp[0]=dp[1]=…=dp[5]=0）。

遍历开始（i从1到5）

1. i=1（s[1]=‘)’）

• 条件：s[1]=‘)’，进入判断；
• 情况1：s[0]=‘(’（基础"()"配对）；
• 计算dp[1]：i=1<2 → dp[1] = 0 + 2 = 2；
• 更新maxans：max(0,2)=2；
• 此时：dp=[0,2,0,0,0,0]，maxans=2。

2. i=2（s[2]=‘(’）

• 条件：s[2]是’('，不处理；
• dp[2]保持0，maxans仍为2；
• 此时：dp=[0,2,0,0,0,0]，maxans=2。

3. i=3（s[3]=‘(’）

• 条件：s[3]是’('，不处理；
• dp[3]保持0，maxans仍为2；
• 此时：dp=[0,2,0,0,0,0]，maxans=2。

4. i=4（s[4]=‘)’）

• 条件：s[4]=‘)’，进入判断；
• 情况1：s[3]=‘(’（基础"()"配对）；
• 计算dp[4]：i=4≥2 → dp[4] = dp[2]（0） + 2 = 2；
• 更新maxans：max(2,2)=2；
• 此时：dp=[0,2,0,0,2,0]，maxans=2。

5. i=5（s[5]=‘)’，核心步骤）

• 条件：s[5]=‘)’，进入判断；
• 情况1不满足（s[4]=‘)’），进入情况2；
• 先算关键值：dp[i-1]=dp[4]=2；
• 验证条件：i – dp[i-1] = 5-2=3 >0，且 s[3-1]=s[2]=‘(’（匹配）；
• 计算dp[5]：
  • 第一部分：dp[4]=2；
  • 第二部分：i-dp[i-1]=3 ≥2 → dp[3-2]=dp[1]=2；
  • 第三部分：+2；
  • 总计：dp[5] = 2 + 2 + 2 = 6；
• 更新maxans：max(2,6)=6；
• 此时：dp=[0,2,0,0,2,6]，maxans=6。

最终结果 遍历结束，返回maxans=6（对应整个字符串"()(())"是最长有效括号，长度6）。

如果本篇文章对您有帮助，可以点赞，收藏或评论哦！！！关注主包不迷路，让我们一起向前进步吧！！