核心思想
动态规划：用空间代替重复计算，
知道怎么算的算法 vs 知道怎么试的算法
有些递归在展开计算时，总是重复调用同一个子问题的解，这种重复调用的递归变成动态规划很有收益 如果每次展开都是不同的解，或者重复调用的现象很少，那么没有改动态规划的必要 下节课会举例，哪些递归没有必要改动态规划的必要
任何动态规划问题都一定对应着一个有重复调用行为的递归 所以任何动态规划的题目都一定可以从递归入手，逐渐实现动态规划的方法 题目 1 到题目 4，都从递归入手，逐渐改出动态规划的实现
尝试策略就是转移方程，完全一回事！ 推荐从尝试入手，因为代码好写，并且一旦发现尝试错误，重新想别的递归代价轻！
当熟悉了从递归到动态规划的转化过程 那么就可以纯粹用动态规划的视角来分析问题了 题目 5 到题目 8，都是纯粹用动态规划的视角来分析、优化的
动态规划的大致过程： 想出设计优良的递归尝试 (方法、经验、固定套路很多)，有关尝试展开顺序的说明 -> 记忆化搜索 (从顶到底的动态规划) ，如果每个状态的计算枚举代价很低，往往到这里就可以了 -> 严格位置依赖的动态规划 (从底到顶的动态规划) ，更多是为了下面说的进一步优化枚举做的准备 -> 进一步优化空间（空间压缩），一维、二维、多维动态规划都存在这种优化 -> 进一步优化枚举也就是优化时间（本节没有涉及，但是后续巨多内容和这有关）
解决一个问题，可能有很多尝试方法 众多的尝试方法中，可能若干的尝试方法有重复调用的情况，可以转化成动态规划 若干个可以转化成动态规划的方法中，又可能有优劣之分 判定哪个是最优的动态规划方法，依据来自题目具体参数的数据量 最优的动态规划方法实现后，后续又有一整套的优化技巧
例题
1 、斐波拉契数
题目描述： 斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给定 n ，请计算 F(n) 。
示例 1：
输入：n = 2 输出：1 解释：F(2) = F(1) + F(0) = 1 + 0 = 1
示例 2：
输入：n = 3 输出：2 解释：F(3) = F(2) + F(1) = 1 + 1 = 2
示例 3：
输入：n = 4 输出：3 解释：F(4) = F(3) + F(2) = 2 + 1 = 3
提示：
0 <= n <= 30
这个题本身不难，主要是依据这个题的递归，去慢慢感受动态规划的转变。
在最开始的 fib 1 方法中，我们直接使用递归的方式，发现对于递归的展开，每一个斐波拉契数都会展开成一个二叉树，其子节点为 fib 1 (n-1) 和 fib 1 (n-2)，在这其中每次哪怕之前已经计算过，到了后续节点又会重复计算。时间复杂度达到了 O( 2^n )
因此由 fib 1 的递归有太多相同的重复计算，且重复计算出来的值每次都是一样的，因此我们用空间 dp换时间就来了动态规划fib 2，每次计算后的值保存在 dp 数组中，这样时间复杂度降为 O (n)
观察 fib 2，我们发现这都是自顶向下的计算，发现他仍然是有递归的过程的，能否利用动态规划但是简化掉递归呢,它可以改为自底向上的，于是就由了 fib 3
但是 fib 3 的计算中，我们还能在空间上再次优化一点，就有了 fib 4.
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code01_FibonacciNumber
* @description:斐波那契数
* // 斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列
* // 该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。
* // 也就是：F(0) = 0，F(1) = 1
* // F(n) = F(n - 1) + F(n - 2)，其中 n > 1
* // 给定 n ，请计算 F(n)
* // 测试链接 : https://leetcode.cn/problems/fibonacci-number/
* @author: zs宝
* @create: 2025-07-28 10:37
* @Version 1.0
**/
package main.java.class066;
import java.util.Arrays;
public class Code01_FibonacciNumber {
class Solution {
public int fib(int n) {
return fib4(n);
}
/**
递归的方式求解
*/
public int fib1(int n){
if(n==0){
return 0;
}
if(n==1){
return 1;
}
return fib1(n-1)+fib1(n-2);
}
/**
由f1的递归转为动态规划的过程
*/
public int fib2(int n){
//存储重复计算的中间值
int[]dp=new int[n+1];
Arrays.fill(dp,-1);
return f2(n,dp);
}
/**
自顶向下
*/
public int f2(int i,int[]dp){
if(i==0){
return 0;
}
if(i==1){
return 1;
}
if(dp[i]!=-1){
return dp[i];
}
int ans=f2(i-1,dp)+f2(i-2,dp);
dp[i]=ans;
return ans;
}
/**
自底向上
*/
public int fib3(int n){
if(n==0){
return 0;
}
if(n==1){
return 1;
}
int[]dp=new int[n+1];
dp[1]=1;
for(int i=2;i<=n;i++){
dp[i]=dp[i-1]+dp[i-2];
}
return dp[n];
}
/**
由fib3的自底向上，进一步优化
*/
public int fib4(int n){
if(n==0){
return 0;
}
if(n==1){
return 1;
}
int lastLast=0;
int last=1;
for(int i=2;i<=n;i++){
int cur=last+lastLast;
lastLast=last;
last=cur;
}
return last;
}
}
}2、最低票价
题目描述 在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行。在接下来的一年里，你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1 到 365 的整数。
火车票有 三种不同的销售方式 ：
一张 为期一天 的通行证售价为
costs[0]美元；一张 为期七天 的通行证售价为
costs[1]美元；一张 为期三十天 的通行证售价为
costs[2]美元。
通行证允许数天无限制的旅行。 例如，如果我们在第 2 天获得一张 为期 7 天 的通行证，那么我们可以连着旅行 7 天：第 2 天、第 3 天、第 4 天、第 5 天、第 6 天、第 7 天和第 8 天。
返回 你想要完成在给定的列表 days 中列出的每一天的旅行所需要的最低消费 。
示例 1：
输入：days = [1,4,6,7,8,20], costs = [2,7,15] 输出：11 解释： 例如，这里有一种购买通行证的方法，可以让你完成你的旅行计划： 在第 1 天，你花了 costs[0] = 2 买了一张为期 1 天的通行证，它将在第 1 天生效。 在第 3 天，你花了 costs[1] = 7 买了一张为期 7 天的通行证，它将在第 3, 4, ..., 9 天生效。 在第 20 天，你花了 costs[0] = 2 买了一张为期 1 天的通行证，它将在第 20 天生效。 你总共花了 11，并完成了你计划的每一天旅行。
示例 2：
输入：days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15] 输出：17 解释： 例如，这里有一种购买通行证的方法，可以让你完成你的旅行计划： 在第 1 天，你花了 costs[2] = 15 买了一张为期 30 天的通行证，它将在第 1, 2, ..., 30 天生效。 在第 31 天，你花了 costs[0] = 2 买了一张为期 1 天的通行证，它将在第 31 天生效。 你总共花了 $17，并完成了你计划的每一天旅行。
提示：
1 <= days.length <= 3651 <= days[i] <= 365days按顺序严格递增costs.length == 31 <= costs[i] <= 1000
这个题同上一个题一样，主要是从递归入手（注意这个题递归必超时），然后变为动态规划，再看看能否优化动态规划的过程。
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code02_MinimumCostForTickets
* @description:最低票价
* // 在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行
* // 在接下来的一年里，你要旅行的日子将以一个名为 days 的数组给出
* // 每一项是一个从 1 到 365 的整数
* // 火车票有 三种不同的销售方式
* // 一张 为期1天 的通行证售价为 costs[0] 美元
* // 一张 为期7天 的通行证售价为 costs[1] 美元
* // 一张 为期30天 的通行证售价为 costs[2] 美元
* // 通行证允许数天无限制的旅行
* // 例如，如果我们在第 2 天获得一张 为期 7 天 的通行证
* // 那么我们可以连着旅行 7 天(第2~8天)
* // 返回 你想要完成在给定的列表 days 中列出的每一天的旅行所需要的最低消费
* // 测试链接 : https://leetcode.cn/problems/minimum-cost-for-tickets/
* @author: zs宝
* @create: 2025-07-28 11:13
* @Version 1.0
**/
package main.java.class066;
import java.util.Arrays;
public class Code02_MinimumCostForTickets {
class Solution {
//对应于3种costs的时间
public static int[]duration=new int[]{1,7,30};
public static int mincostTickets(int[] days, int[] costs) {
return mincostTickets3(days,costs);
}
/**
纯递归的方式
这种方式会超时 */
public static int mincostTickets1(int[] days,int[]costs){
return f1(days,costs,0);
}
/**
递归求解从第i天算，最低花费多少
*/
public static int f1(int[] days,int[]costs,int i){
//旅游天数用完，直接返回0
if(i==days.length){
return 0;
}
int ans=Integer.MAX_VALUE;
//分别在第i天开始用3种costs方式计算之后的旅游花费
//记录最小的那个
for(int k=0,j=i;k<3;k++){
while(j<days.length && days[i]+duration[k]>days[j]){
j++;
}
ans=Math.min(ans,costs[k]+f1(days,costs,j));
}
return ans;
}
//由于递归会超时
//递归每轮要计算多次前面轮已经计算过的东西
//且每次已经计算过的东西，在后面轮重复计算时，结果时一样的
//因此我们用空间换时间记忆化搜索，进行动态规划
//可以通过本题
public static int mincostTickets2(int[] days,int[]costs){
int[]dp=new int[days.length+1];
for (int i = 0; i < days.length; i++) {
dp[i] = Integer.MAX_VALUE;
}
return f2(days,costs,0,dp);
}
//动态规划求解
// 从顶到底的动态规划
public static int f2(int[] days,int[]costs,int i,int[]dp){
if(i==days.length){
return 0;
}
if(dp[i]!=Integer.MAX_VALUE){
return dp[i];
}
int ans=Integer.MAX_VALUE;
//分别在第i天开始用3种costs方式计算之后的旅游花费
//记录最小的那个
for(int k=0,j=i;k<3;k++){
while(j<days.length && days[i]+duration[k]>days[j]){
j++;
}
ans=Math.min(ans,costs[k]+f2(days,costs,j,dp));
}
dp[i]=ans;
return ans;
}
//现在根据自顶向下的动态规划，我们尝试进行优化
//使其变为自底向上的方式，进一步优化时间
public static int MAXN=366;
public static int[]dp=new int[MAXN];
public static int mincostTickets3(int[] days,int[]costs){
int n=days.length;
Arrays.fill(dp,0,n+1,Integer.MAX_VALUE);
dp[n]=0;
//自底向上，从后往前，一次性全部算完
for(int i=n-1;i>=0;i--){
for(int k=0,j=i;k<3;k++){
while(j<n && days[i]+duration[k]>days[j]){
j++;
}
dp[i]=Math.min(dp[i],costs[k]+dp[j]);
}
}
return dp[0];
}
}
}3、解码方法
题目描述： 一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：
"1" -> 'A' "2" -> 'B' ... "25" -> 'Y' "26" -> 'Z'
然而，在 解码 已编码的消息时，你意识到有许多不同的方式来解码，因为有些编码被包含在其它编码当中（"2" 和 "5" 与 "25"）。
例如，"11106" 可以映射为：
"AAJF"，将消息分组为(1, 1, 10, 6)"KJF"，将消息分组为(11, 10, 6)消息不能分组为
(1, 11, 06)，因为"06"不是一个合法编码（只有 "6" 是合法的）。
注意，可能存在无法解码的字符串。
给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。如果没有合法的方式解码整个字符串，返回 0。
题目数据保证答案肯定是一个 32 位 的整数。
示例 1：
输入：s = "12" 输出：2 解释：它可以解码为 "AB"（1 2）或者 "L"（12）。
示例 2：
输入：s = "226" 输出：3 解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
示例 3：
输入：s = "06" 输出：0 解释："06" 无法映射到 "F" ，因为存在前导零（"6" 和 "06" 并不等价）。
提示：
1 <= s.length <= 100s只包含数字，并且可能包含前导零。
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code03_DecodeWays
* @description:解码方法
* // 一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：
* // 'A' -> "1"
* // 'B' -> "2" * // ... * // 'Z' -> "26" * // 要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）
* // 例如，"11106" 可以映射为："AAJF"、"KJF"
* // 注意，消息不能分组为(1 11 06)，因为 "06" 不能映射为 "F"
* // 这是由于 "6" 和 "06" 在映射中并不等价
* // 给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数
* // 题目数据保证答案肯定是一个 32位 的整数
* // 测试链接 : https://leetcode.cn/problems/decode-ways/
* @author: zs宝
* @create: 2025-07-29 10:07
* @Version 1.0
**/
package main.java.class066;
import java.util.Arrays;
public class Code03_DecodeWays {
class Solution {
public static int numDecodings(String s) {
return numDecodings4(s);
}
/**
递归的版本，纯递归
*/
public static int numDecodings1(String s) {
return f1(s.toCharArray(),0);
}
/**
从i位置开始有多少种可能
*/
public static int f1(char[]s,int i){
int n=s.length;
if(i==n){
return 1;
}
//主要分析的这一块
int ans=0;
if(s[i]=='0'){
return 0;
}else{
//当只算当前字符为一个时，即i,i+1位置不看作同一个
ans+=f1(s,i+1);
//当即i,i+1位置不看作同一个时
if(i+1<n && (s[i]-'0')*10+(s[i+1]-'0')<=26){
ans+=f1(s,i+2);
}
}
return ans;
}
/**
从递归优化而来
由递归改为动态规划 动态规划：记忆化搜索 自顶向下 */
public static int MAXN=101;
public static int[]dp=new int[MAXN];
public static int numDecodings2(String s) {
Arrays.fill(dp,0,s.length()+1,-1);
return f2(s.toCharArray(),0);
}
public static int f2(char[]s,int i){
int n=s.length;
if(i==n){
return 1;
}
if(dp[i]!=-1){
return dp[i];
}
//主要分析的这一块
int ans=0;
if(s[i]=='0'){
return 0;
}else{
//当只算当前字符为一个时，即i,i+1位置不看作同一个
ans+=f2(s,i+1);
//当即i,i+1位置不看作同一个时
if(i+1<n && (s[i]-'0')*10+(s[i+1]-'0')<=26){
ans+=f2(s,i+2);
}
}
dp[i]=ans;
return ans;
}
/**
动态规划，自底向上
*/
public static int numDecodings3(String s){
Arrays.fill(dp,0,s.length()+1,-1);
return f3(s.toCharArray(),0);
}
public static int f3(char[]s,int k){
int n=s.length;
dp[n]=1;
for(int i=n-1;i>=0;i--){
if(s[i]=='0'){
dp[i]=0;
}else{
dp[i]=dp[i+1];
if(i+1<n && (s[i]-'0')*10+(s[i+1]-'0')<=26){
dp[i]+=dp[i+2];
}
}
}
return dp[k];
}
/**
根据自底向上的动态规划优化
严格依赖位置的动态规划+空间压缩
*/
public static int numDecodings4(String s){
return f4(s.toCharArray());
}
public static int f4(char[]s){
int n=s.length;
int next=1;
int nextNext=0;
for(int i=n-1;i>=0;i--){
int cur;
if(s[i]=='0'){
cur=0;
}else{
cur=next;
if(i+1<n && (s[i]-'0')*10+(s[i+1]-'0')<=26){
cur+=nextNext;
}
}
nextNext=next;
next=cur;
}
return next;
}
}
}4、解码方法Ⅱ
题目描述： 一条包含字母 A-Z 的消息通过以下的方式进行了 编码 ：
'A' -> "1" 'B' -> "2" ... 'Z' -> "26"
要 解码 一条已编码的消息，所有的数字都必须分组，然后按原来的编码方案反向映射回字母（可能存在多种方式）。例如，"11106" 可以映射为：
"AAJF"对应分组(1 1 10 6)"KJF"对应分组(11 10 6)
注意，像 (1 11 06) 这样的分组是无效的，因为 "06" 不可以映射为 'F' ，因为 "6" 与 "06" 不同。
除了 上面描述的数字字母映射方案，编码消息中可能包含 '*' 字符，可以表示从 '1' 到 '9' 的任一数字（不包括 '0'）。例如，编码字符串 "1*" 可以表示 "11"、"12"、"13"、"14"、"15"、"16"、"17"、"18" 或 "19" 中的任意一条消息。对 "1*" 进行解码，相当于解码该字符串可以表示的任何编码消息。
给你一个字符串 s ，由数字和 '*' 字符组成，返回 解码 该字符串的方法 数目 。
由于答案数目可能非常大，返回 109 + 7 的 模 。
示例 1：
输入：s = "" 输出：9 解释：这一条编码消息可以表示 "1"、"2"、"3"、"4"、"5"、"6"、"7"、"8" 或 "9" 中的任意一条。 可以分别解码成字符串 "A"、"B"、"C"、"D"、"E"、"F"、"G"、"H" 和 "I" 。 因此，"" 总共有 9 种解码方法。
示例 2：
输入：s = "1" 输出：18 解释：这一条编码消息可以表示 "11"、"12"、"13"、"14"、"15"、"16"、"17"、"18" 或 "19" 中的任意一条。 每种消息都可以由 2 种方法解码（例如，"11" 可以解码成 "AA" 或 "K"）。 因此，"1" 共有 9 * 2 = 18 种解码方法。
示例 3：
输入：s = "2" 输出：15 解释：这一条编码消息可以表示 "21"、"22"、"23"、"24"、"25"、"26"、"27"、"28" 或 "29" 中的任意一条。 "21"、"22"、"23"、"24"、"25" 和 "26" 由 2 种解码方法，但 "27"、"28" 和 "29" 仅有 1 种解码方法。 因此，"2" 共有 (6 2) + (3 1) = 12 + 3 = 15 种解码方法。
提示：
1 <= s.length <= 105s[i]是0 - 9中的一位数字或字符'*
这个题是第 3 题的变种，比起第 3 题有了更多的分类讨论 
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code04_DecodeWaysII
* @description: 解码方法 II
* // 一条包含字母 A-Z 的消息通过以下的方式进行了 编码 ：
* // 'A' -> "1"
* // 'B' -> "2" * // ... * // 'Z' -> "26" * // 要 解码 一条已编码的消息，所有的数字都必须分组
* // 然后按原来的编码方案反向映射回字母（可能存在多种方式）
* // 例如，"11106" 可以映射为："AAJF"、"KJF"
* // 注意，像 (1 11 06) 这样的分组是无效的，"06"不可以映射为'F'
* // 除了上面描述的数字字母映射方案，编码消息中可能包含 '*' 字符
* // 可以表示从 '1' 到 '9' 的任一数字（不包括 '0'）
* // 例如，"1*" 可以表示 "11"、"12"、"13"、"14"、"15"、"16"、"17"、"18" 或 "19"
* // 对 "1*" 进行解码，相当于解码该字符串可以表示的任何编码消息
* // 给你一个字符串 s ，由数字和 '*' 字符组成，返回 解码 该字符串的方法 数目
* // 由于答案数目可能非常大，答案对 1000000007 取模
* // 测试链接 : https://leetcode.cn/problems/decode-ways-ii/
* @author: zs宝
* @create: 2025-07-29 11:03
* @Version 1.0
**/
package main.java.class066;
import java.util.Arrays;
public class Code04_DecodeWaysII {
class Solution {
public static int numDecodings(String s) {
return numDecodings4(s);
}
/**
递归解法：会超时，并且由于没有取模，运算结果会超大
*/
public static int numDecodings1(String s) {
return f1(s.toCharArray(), 0);
}
public static int f1(char[] s, int i) {
int n = s.length;
if (i == n) {
return 1;
}
int ans = 0;
if (s[i] == '0') {
return 0;
}
//开始分类讨论
//只占一位的时候
ans += (s[i] == '*' ? 9 : 1) * f1(s, i + 1);
//占2位的时候
if (i + 1 < n) {
//当第一位不为*时
if (s[i] != '*') {
//两位是都是num的时候
if (s[i + 1] != '*') {
if ((s[i] - '0') * 10 + (s[i + 1] - '0') <= 26) {
ans += f1(s, i + 2);
}
//第一位数字为num,第二位数字为*的时候
} else {
if (s[i] == '1') {
ans += 9 * f1(s, i + 2);
} else if (s[i] == '2') {
ans += 6 * f1(s, i + 2);
}
}
//当第一位为*时
} else {
//当第一位为* 第二位为num时
if (s[i + 1] != '*') {
if (s[i + 1] <= '6') {
ans += 2 * f1(s, i + 2);
} else {
ans += f1(s, i + 2);
}
//当第一位为* 第二位也为*时
} else {
ans += 15 * f1(s, i + 2);
}
}
}
return ans;
}
public static long mod = 1000000007;
public static int MAXN = 100001;
public static long[] dp = new long[MAXN];
/**
由递归而来的动态规划
动态规划：自顶向下 记忆化搜索 */
public static int numDecodings2(String s) {
Arrays.fill(dp, 0, s.length() + 1, -1);
dp[s.length()] = 1;
return (int) f2(s.toCharArray(), 0);
}
public static long f2(char[] s, int i) {
int n = s.length;
if (i == n) {
return 1;
}
long ans = 0;
if (s[i] == '0') {
return 0;
}
if (dp[i] != -1) {
return dp[i];
}
//开始分类讨论
//只占一位的时候
ans += (s[i] == '*' ? 9 : 1) * f2(s, i + 1);
//占2位的时候
if (i + 1 < n) {
//当第一位不为*时
if (s[i] != '*') {
//两位是都是num的时候
if (s[i + 1] != '*') {
if ((s[i] - '0') * 10 + (s[i + 1] - '0') <= 26) {
ans += f2(s, i + 2);
}
//第一位数字为num,第二位数字为*的时候
} else {
if (s[i] == '1') {
ans += 9 * f2(s, i + 2);
} else if (s[i] == '2') {
ans += 6 * f2(s, i + 2);
}
}
//当第一位为*时
} else {
//当第一位为* 第二位为num时
if (s[i + 1] != '*') {
if (s[i + 1] <= '6') {
ans += 2 * f2(s, i + 2);
} else {
ans += f2(s, i + 2);
}
//当第一位为* 第二位也为*时
} else {
ans += 15 * f2(s, i + 2);
}
}
}
ans %= mod;
dp[i] = ans;
return ans;
}
/**
根据记忆化搜索的动态规划改为
严格依照位置的自底向上的动态规划 */
public static int numDecodings3(String str) {
char[]s=str.toCharArray();
int n=s.length;
Arrays.fill(dp, 0, n + 1, 0);
dp[n] = 1;
for (int i = n - 1; i >= 0; i--) {
if (s[i] != '0') {
dp[i] = (s[i] == '*' ? 9 : 1) * dp[i+1];
//占2位的时候
if (i + 1 < n) {
//当第一位不为*时
if (s[i] != '*') {
//两位是都是num的时候
if (s[i + 1] != '*') {
if ((s[i] - '0') * 10 + (s[i + 1] - '0') <= 26) {
dp[i] += dp[i+2];
}
//第一位数字为num,第二位数字为*的时候
} else {
if (s[i] == '1') {
dp[i] += 9 * dp[i+2];
} else if (s[i] == '2') {
dp[i] += 6 * dp[i+2];
}
}
//当第一位为*时
} else {
//当第一位为* 第二位为num时
if (s[i + 1] != '*') {
if (s[i + 1] <= '6') {
dp[i] += 2 * dp[i+2];
} else {
dp[i] += dp[i+2];
}
//当第一位为* 第二位也为*时
} else {
dp[i] += 15 * dp[i+2];
}
}
}
dp[i]%=mod;
}
}
return (int)dp[0];
}
/**
优化严格依照位置的自底向上的动态规划
*/
public static int numDecodings4(String str) {
char[]s=str.toCharArray();
int n=s.length;
long nextNext=0;
long next=1;
long cur=0;
for (int i = n - 1; i >= 0; i--) {
if (s[i] != '0') {
cur = (s[i] == '*' ? 9 : 1) * next;
//占2位的时候
if (i + 1 < n) {
//当第一位不为*时
if (s[i] != '*') {
//两位是都是num的时候
if (s[i + 1] != '*') {
if ((s[i] - '0') * 10 + (s[i + 1] - '0') <= 26) {
cur += nextNext;
}
//第一位数字为num,第二位数字为*的时候
} else {
if (s[i] == '1') {
cur += 9 * nextNext;
} else if (s[i] == '2') {
cur += 6 * nextNext;
}
}
//当第一位为*时
} else {
//当第一位为* 第二位为num时
if (s[i + 1] != '*') {
if (s[i + 1] <= '6') {
cur += 2 * nextNext;
} else {
cur += nextNext;
}
//当第一位为* 第二位也为*时
} else {
cur += 15 * nextNext;
}
}
}
cur%=mod;
}
nextNext=next;
next=cur;
cur=0;
}
return (int)next;
}
}
}5、丑数Ⅱ
题目描述： 给你一个整数 n ，请你找出并返回第 n 个 丑数 。
丑数 就是质因子只包含 2、3 和 5 的正整数。
示例 1：
输入：n = 10 输出：12 解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
示例 2：
输入：n = 1 输出：1 解释：1 通常被视为丑数。
提示：
1 <= n <= 1690
这道题最容易想到的解法就是一个一个的枚举判断，但是这样的解法必定会超时，所以我们想要通过这个暴力递归的解法去进行优化。最简单的就是记忆化搜索的动态规划，但是仔细看暴力递归的解法，这个题本身并不适合记忆化搜索。因为这个它的状态转移过程中 并没有出现大量“重复子问题”的递归调用，也就是说，它不是那种“最适合自顶向下缓存结果”的问题。 记忆化搜索的本质是什么？
记忆化搜索（递归 + 缓存）适用于 有重叠子问题 的场景。
比如斐波那契、背包、树形 DP 等，同一个状态
f(i, j)可能会被多个路径反复调用，所以缓存非常有效。 而这道题逐个生成丑数x，然后再将x*2, x*3, x*5作为候选放入集合或堆中，每一个生成出来的x, 我们都只会处理一次，也就是说状态转移的过程并没有重复子问题的调用。 这类不断扩展状态，不会走回头路”的问题，更适合“前向构造式”的动态规划，而不是“回溯式”的记忆化搜索。 最后的最优解法流程如下
+----------+----------+----------+
指针位置 | p2 | p3 | p5 |
|----------|----------|----------|
当前值 | dp[p2]=1 | dp[p3]=1 | dp[p5]=1 |
候选丑数 | 1×2 = 2 | 1×3 = 3 | 1×5 = 5 |
选最小加入 | min(2, 3, 5) = 2，加入 dp[1] |
更新指针 | p2++ |
----------------------------------------------------------
指针位置 | p2=1 | p3=0 | p5=0 |
当前值 | dp[p2]=2 | dp[p3]=1 | dp[p5]=1 |
候选丑数 | 2×2 = 4 | 1×3 = 3 | 1×5 = 5 |
选最小加入 | min(4, 3, 5) = 3，加入 dp[2] |
更新指针 | p3++ |
----------------------------------------------------------
指针位置 | p2=1 | p3=1 | p5=0 |
当前值 | dp[p2]=2 | dp[p3]=2 | dp[p5]=1 |
候选丑数 | 2×2 = 4 | 2×3 = 6 | 1×5 = 5 |
选最小加入 | min(4, 6, 5) = 4，加入 dp[3] |
更新指针 | p2++ |
----------------------------------------------------------
指针位置 | p2=2 | p3=1 | p5=0 |
当前值 | dp[p2]=3 | dp[p3]=2 | dp[p5]=1 |
候选丑数 | 3×2 = 6 | 2×3 = 6 | 1×5 = 5 |
选最小加入 | min(6, 6, 5) = 5，加入 dp[4] |
更新指针 | p5++ |
----------------------------------------------------------
... 依此类推，直到填满 dp[9]
代码
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code05_UglyNumberII
* @description: 丑数 II
* 给你一个整数 n ，请你找出并返回第 n 个 丑数
* 丑数 就是只包含质因数 2、3 或 5 的正整数
* 测试链接 : https://leetcode.cn/problems/ugly-number-ii/
* @author: zs宝
* @create: 2025-07-31 10:03
* @Version 1.0
**/
package main.java.class066;
public class Code05_UglyNumberII {
//纯递归枚举的解法：超时
class Solution1 {
public int nthUglyNumber(int n) {
int count = 0;
int num = 1;
while (true) {
if (isUgly(num)) {
count++;
if (count == n) return num;
}
num++;
}
}
private boolean isUgly(int num) {
if (num <= 0) return false;
for (int factor : new int[]{2, 3, 5}) {
while (num % factor == 0) num /= factor;
}
return num == 1;
}
}
//优先级队列的解法：能过时间复杂度O(nlogn)
class Solution2 {
public int nthUglyNumber(int n) {
PriorityQueue<Long> queue = new PriorityQueue<>();
Set<Long> seen = new HashSet<>();
queue.add(1L);
seen.add(1L);
long cur = 1;
for (int i = 0; i < n; i++) {
cur = queue.poll();
long[] factors = {2, 3, 5};
for (long factor : factors) {
long next = cur * factor;
if (seen.add(next)) { // add 如果本来就存在则返回 false queue.add(next);
}
}
}
return (int) cur;
}
}
//根据动态规划的解法O(n)
class Solution3 {
public int nthUglyNumber(int n) {
int[]dp=new int[n+1];
dp[1]=1;
for(int i=2,i1=1,i2=1,i3=1,cur;i<=n;i++){
int a=dp[i1]*2;
int b=dp[i2]*3;
int c=dp[i3]*5;
cur=Math.min(Math.min(a,b),c);
if(cur==a){
i1++;
}
if(cur==b){
i2++;
}
if(cur==c){
i3++;
}
dp[i]=cur;
}
return dp[n];
}
}
}6、最长有效括号
题目描述： 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
示例 1：
输入：s = "(()" 输出：2 解释：最长有效括号子串是 "()"
示例 2：
输入：s = ")()())" 输出：4 解释：最长有效括号子串是 "()()"
示例 3：
输入：s = "" 输出：0
提示：
0 <= s.length <= 3 * 104s[i]为'('或')'
首先尝试暴力的解法 后续根据暴力解法进行演变 定义 dp[i]为子串必须以i位置的字符结尾的情况下，往左整体有效的最大长度 并定义状态转移公式
s.charAt(i) == ')'才可能更新dp[i]若
s[i-1] == '('：形成 "()"，则dp[i] = dp[i-2] + 2若
s[i-1] == ')'且s[i - dp[i-1] - 1] == '('：则dp[i] = dp[i-1] + 2 + dp[i - dp[i-1] - 2]
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code06_LongestValidParentheses
* @description:最长有效括号
* // 给你一个只包含 '(' 和 ')' 的字符串
* // 找出最长有效（格式正确且连续）括号子串的长度。
* // 测试链接 : https://leetcode.cn/problems/longest-valid-parentheses/
* @author: zs宝
* @create: 2025-07-31 11:19
* @Version 1.0
**/
package main.java.class066;
public class Code06_LongestValidParentheses {
//暴力解法，超时
class Solution1 {
public int longestValidParentheses(String s) {
int n=s.length();
int maxLen=0;
//以当前字符开头，去判断当前字符开头的最长子串长度
for(int i=0;i<n;i++){
//配对肯定是偶数的长度，因此每次j+=2;
for(int j=i+2;j<=n;j+=2){
if(isValid(s.substring(i,j))){
maxLen=Math.max(maxLen,j-i);
}
}
}
return maxLen;
}
public boolean isValid(String str){
int balance=0;
for(char ch:str.toCharArray()){
if(ch=='('){
balance++;
}else{
balance--;
}
//这里这个判断表示每一轮循环后，必须判断banlance是否小于0
//防止))((这类情况
if(balance<0){
return false;
}
}
return balance==0;
}
}
//动态规划
class Solution2 {
public int longestValidParentheses(String s) {
char[]str=s.toCharArray();
int n=str.length;
//dp[i] : 子串必须以i位置的字符结尾的情况下，往左整体有效的最大长度
int[]dp=new int[n];
int ans=0;
for(int i=1,p;i<n;i++){
if(str[i]==')'){
p=i-dp[i-1]-1;
if(p>=0 && str[p]=='('){
dp[i]=dp[i-1]+2+(p-1>=0?dp[p-1]:0);
}
}
ans=Math.max(ans,dp[i]);
}
return ans;
}
}
}7、环绕字符串中唯一的子字符串
题目描述： 定义字符串 base 为一个 "abcdefghijklmnopqrstuvwxyz" 无限环绕的字符串，所以 base 看起来是这样的：
"...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".
给你一个字符串 s ，请你统计并返回 s 中有多少 不同**非空子串** 也在 base 中出现。
示例 1：
输入：s = "a" 输出：1 解释：字符串 s 的子字符串 "a" 在 base 中出现。
示例 2：
输入：s = "cac" 输出：2 解释：字符串 s 有两个子字符串 ("a", "c") 在 base 中出现。
示例 3：
输入：s = "zab" 输出：6 解释：字符串 s 有六个子字符串 ("z", "a", "b", "za", "ab", and "zab") 在 base 中出现。
提示：
1 <= s.length <= 105s 由小写英文字母组成
错误代码
class Solution {
public int findSubstringInWraproundString(String str) {
char[] s=str.toCharArray();
int n=s.length;
//定义dp[i]为必须以i结尾的字符串中有多少子串是符合要求的
int[]dp=new int[n+1];
//将小写字母转换为整形数组
int[]convert=new int[n];
for(int i=0;i<n;i++){
convert[i]=s[i]-'a';
}
//记录某个字符出现了几次
Set<Integer> set=new HashSet<>();
Set<String> set_s=new HashSet<>();
dp[0]=1;
set.add(convert[0]);
set_s.add(str.substring(0,1));
for(int i=1;i<n;i++){
if(set.add(convert[i])){
dp[i]++;
//用 substring(i-dp[i], i+1) 手动拼接,时间复杂度暴增
set_s.add(str.substring(i,i+1));
}
if((convert[i-1]+1)%26==convert[i]){
if(dp[i-1]==0){
//`i - dp[i]` 这个位置也并不一定是合法连续串的起点位置，完全错乱
if(set_s.add(str.substring(i-1,i+1))){
dp[i]++;
}
}else{
//试图用 `Set<String>` 手动去重，但却只添加“尾段子串”
if(set_s.add(str.substring(i-dp[i],i+1))){
dp[i]+=dp[i-1];
}
}
}
}
int ans=0;
for(int i=0;i<n;i++){
//System.out.println(dp[i]);
ans+=dp[i];
}
return ans;
}
}正确解法：
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code07_UniqueSubstringsWraparoundString
* @description: 环绕字符串中唯一的子字符串
* // 定义字符串 base 为一个 "abcdefghijklmnopqrstuvwxyz" 无限环绕的字符串
* // 所以 base 看起来是这样的：
* // "..zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd.."
* // 给你一个字符串 s ，请你统计并返回 s 中有多少 不同非空子串 也在 base 中出现
* // 测试链接 : https://leetcode.cn/problems/unique-substrings-in-wraparound-string/
* @author: zs宝
* @create: 2025-08-04 08:57
* @Version 1.0
**/
package main.java.class066;
import java.util.HashSet;
import java.util.Set;
public class Code07_UniqueSubstringsWraparoundString {
//暴力递归
public class Solution1 {
public int findSubstringInWraproundString(String s) {
Set<String> set = new HashSet<>();
int n = s.length();
for (int i = 0; i < n; i++) {
StringBuilder sb = new StringBuilder();
sb.append(s.charAt(i));
set.add(sb.toString());
for (int j = i + 1; j < n; j++) {
char prev = s.charAt(j - 1);
char curr = s.charAt(j);
if ((curr - prev + 26) % 26 == 1) {
sb.append(curr);
set.add(sb.toString());
} else {
break;
}
}
}
return set.size();
}
}
//记忆化搜索的动态规划
class Solution2 {
public int findSubstringInWraproundString(String str) {
int n=str.length();
int[]s=new int[n];
for(int i=0;i<n;i++){
s[i]=str.charAt(i)-'a';
}
//每个位置对应26个小写字母
//以i结尾的最长连续长度
int[]dp=new int[26];
dp[s[0]]=1;
for(int i=1,cur,pre,len=1;i<n;i++){
cur=s[i];
pre=s[i-1];
//判断字符是否连续
if((pre==25 && cur==0) || (pre+1==cur)){
len++;
}else{
//注意如果不连续要把长度重置
len=1;
}
//这里由于我们dp[i]的定义是以某个字符为结尾的最大长度
//结合题目子串的要求
//这个dp定义就可以实现自动的去重
dp[cur]=Math.max(dp[cur],len);
}
int ans=0;
for(int i=0;i<26;i++){
ans+=dp[i];
}
return ans;
}
}
}错误解法对比正确解法
8、不同的子序列Ⅱ
题目描述： 给定一个字符串 s，计算 s 的 不同非空子序列 的个数。因为结果可能很大，所以返回答案需要对 10^9 + 7 取余 。
字符串的 子序列 是经由原字符串删除一些（也可能不删除）字符但不改变剩余字符相对位置的一个新字符串。
例如，
"ace"是"_**a**_b_**c**_d_**e**_"的一个子序列，但"aec"不是。
示例 1：
输入：s = "abc" 输出：7 解释：7 个不同的子序列分别是 "a", "b", "c", "ab", "ac", "bc", 以及 "abc"。
示例 2：
输入：s = "aba" 输出：6 解释：6 个不同的子序列分别是 "a", "b", "ab", "ba", "aa" 以及 "aba"。
示例 3：
输入：s = "aaa" 输出：3 解释：3 个不同的子序列分别是 "a", "aa" 以及 "aaa"。
提示：
1 <= s.length <= 2000s仅由小写英文字母组成 这道题的解法主要注意，由于是求子序列数量，因此每次对于第 i 个字符可以留下或者不留下两种选择，所以总得结果是对于每个字符要或者不要而成的一颗二叉树（这就是递归的那一套），但是要注意其中的去重。因此每当进行当前字符 （索引为 i）的子序列数量时（这里假设第 i-1 位置结尾有 a 个），那么对于第 i 个字符就有要或者不要两种组合方式，因此让第 i-1 位置结尾的所有子序列对于第 i 位置上的字符要或者不要，那么总共就有 2 * a 个，但是由于要去重，那么上一次同样与第 i 位置的字符结尾的子序列由于要或者不要就会产生重复，如例子s = "abac"第一步：当前：所有旧子序列 =
""加
'a'→ 新增"a"cnt['a'] = 0newAdd = all - cnt['a'] = 1 - 0 = 1cnt['a'] = 1all = 2当前非空子序列："a"第二步旧子序列：
"","a"加
'b'→"b","ab"cnt['b'] = 0newAdd = 2 - 0 = 2cnt['b'] = 2all = 4非空子序列："a","b","ab"第三步：a（重点） 这就是 “去重” 要发生的时刻！ 如果不去重会发生什么？ 会认为所有旧的 4 个子序列（"","a","b","ab") 都可以加'a'，得到："a"（重复了）"aa""ba""aba"一共 4 个新串。 但第一次在第 1 步'a'时，已经生成了"a"那时候就是从""+'a'得到的"a"如果现在再次从""+'a'再生成"a"，就重复了 我们应该减掉：
上一次出现
'a'（第 1 步）时，形成的所有子序列数量
当时的
newAdd = 1就是在那一步加
'a'得到的子串："a" 那时候的cnt['a'] = 1，也正好是那一次新增的所有以'a'结尾的子序列个数 所以现在：newAdd = all - cnt['a'] = 4 - 1 = 3仅生成这 3 个新串："aa""ba""aba"去除了重复的"a"
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code08_DistinctSubsequencesII
* @description: 不同的子序列 II
* // 给定一个字符串 s，计算 s 的 不同非空子序列 的个数
* // 因为结果可能很大，答案对 1000000007 取模
* // 字符串的 子序列 是经由原字符串删除一些（也可能不删除）
* // 字符但不改变剩余字符相对位置的一个新字符串
* // 例如，"ace" 是 "abcde" 的一个子序列，但 "aec" 不是
* // 测试链接 : https://leetcode.cn/problems/distinct-subsequences-ii/
* @author: zs宝
* @create: 2025-08-04 10:47
* @Version 1.0
**/
package main.java.class066;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
public class Code08_DistinctSubsequencesII {
//递归解法，超时
class Solution1 {
Set<String> set=new HashSet<>();
public int distinctSubseqII(String s) {
dfs(s,0,"");
return set.size();
}
public void dfs(String s,int i,String path){
if(i==s.length()){
if(!path.isEmpty()){
set.add(path);
}
return;
}
//要当前字符
dfs(s,i+1,path+s.charAt(i));
//不要当前字符
dfs(s,i+1,path);
}
}
//记忆化搜索的动态规划
//dp[i] = 2 * dp[i - 1] - dp[last[s[i - 1]]]
class Solution2 {
public static int MOD=1000000007;
public static int MAXN=2001;
//dp[i]表示以s[0-i]位置的子序列个数
public static int[]dp=new int[MAXN];
public static boolean[] visited=new boolean[MAXN];
//表示当前字符的最后一次出现位置
public static int[]last=new int[26];
public static int distinctSubseqII(String s) {
Arrays.fill(visited,false);
Arrays.fill(last,-1);
return (dfs(s,s.length(),dp,visited,last)-1+MOD)%MOD;
}
public static int dfs(String s, int i, int[] dp, boolean[] visited, int[] last){
if(i==0){
return 1;
}
if(visited[i]){
return dp[i];
}
int res=dfs(s,i-1,dp,visited,last)*2%MOD;
//找出当前字符的上一次出现位置
//开始去重
//为什么不是i呢，dp中空字符串占了第0个位置
char c=s.charAt(i-1);
int cid=c-'a';
if(last[cid]!=-1){
res = (res - dfs(s, last[cid], dp, visited, last) + MOD) % MOD;
}
dp[i]=res;
visited[i]=true;
last[cid]=i-1;
return res;
}
}
//严格按照位置的动态规划
//根据记忆化搜索优化而来
class Solution3 {
//根据记忆化搜索优化的解法进行优化
// all add
//dp[i]=2*dp[i-1]-dp[last(s[i])]=dp[i-1]+(dp[i-1]-dp[last(s[i])]) public int distinctSubseqII(String str) {
int mod = 1000000007;
char[]s=str.toCharArray();
//上一次以某个字符为结尾的子序列数量
int[]cnt=new int[26];
//总子序列数量,最开始有个空串，最后结果要将其去掉
int all=1;
//比起上一个字符位置，新增的子序列数量
//计算公式为(dp[i-1]-dp[last(s[i])])
int add;
for(char c:s){
//每次求出新增的量
add=(all-cnt[c-'a']+mod)%mod;
//更新上一次以某个字符结尾的子序列数量
cnt[c-'a']=(cnt[c-'a']+add)%mod;
all=(all+add)%mod;
}
return (all-1+mod)%mod;
}
}
}