从递归入手一维动态规划

从递归入手一维动态规划

1. 509. 斐波那契数

1.1 思绪

递归

F(i) = F(i-1) + F(i-2)
每个点都往下睁开两个分支，时间复杂度为 O(2n) 。
在上图中我们可以看到 F(6) = F(5) + F(4)。
盘算 F(6) 的时间已经睁开盘算过 F(5)了。而在盘算 F(7)的时间，还须要再一次睁开盘算 F(5)。

影象化搜刮

我们可以利用一张缓存表记载已经睁开盘算的效果。
上图右侧就是缓存表。
过细看，我们紧张是沿着这棵树的左边不绝盘算，盘算好后将效果记载缓存表中。轮到盘算右边的时间就可以直接返回。
比方我们不绝沿着左边盘算 F(i-3)。
F(i-3) = F(i-4) + F(i-5)。这个过程盘算完后就会把每个函数各自的效果记载到缓存表中。
将F(i-3)的效果返回给F(i-2)。
F(i-2) = F(i-3) + F(i-4)。F(i-3)的效果已经返回，接着盘算F(i-4)。由于F(i-4)之前盘算过，我们直接从缓存表查F(i-4)的效果，返回给F(i-3)即可。
这种做法时间复杂度为O(n)。

自底向上动态规划

1. [0                1                1                2                3                                                 ]
2. 0                1                2                3                4                5                6                7

复制代码

初始情况：arr[0] = 0,arr[1] = 1
arr[2] = arr[1] + arr[0] = 1 + 0 = 1
arr[3] = arr[2] + arr[1] = 1 + 1 = 2
如许从底部不绝向上推，时间复杂度也为O(n)。

滚动数组

1. [0                        1        ]
2. lastLast   last  

复制代码

设置两个变量，lastLast = 0，last = 1。
cur = lastLast + last = 0 + 1 = 1。
之后分别向后移动lastLast 、 last。
lastLast = last
last = cur

1. [0                        1                         1 ]
2.                    lastLast   last  

复制代码

如许就节省了额外空间复杂度O(n)

1.2 代码

1. import java.util.Arrays;
3. /**
4. * @Title: Fib
5. * @Author Wood
6. * @Package leetcode.DynamicProgramming.class66.lc509
7. * @Date 2025/4/8 18:58
8. * @description: https://leetcode.cn/problems/fibonacci-number/
9. */
10. public class Fib {
11.     // 递归
12.     public int fib1(int n) {
13.         return f1(n);
14.     }
16.     // 递归
17.     private int f1(int n) {
18.         if (n == 0){
19.             return 0;
20.         }
22.         if (n == 1){
23.             return 1;
24.         }
26.         return f1(n-1) + f1(n-2);
27.     }
29.     // 记忆化
30.     public int fib2(int n) {
31.         int[] dp = new int[n+1];
32.         Arrays.fill(dp,-1);
34.         return f2(dp,n);
35.     }
37.     // 记忆化
38.     private int f2(int[] dp, int n) {
39.         if (n == 0){
40.             return 0;
41.         }
43.         if (n == 1){
44.             return 1;
45.         }
47.         if (dp[n] != -1){
48.             return dp[n];
49.         }
51.         int ans = f2(dp,n-1) + f2(dp,n-2);
52.         dp[n] = ans;
53.         return ans;
54.     }
56.     // 自底向上动态规划
57.     public int fib3(int n) {
58.         if (n == 0){
59.             return 0;
60.         }
62.         if (n == 1){
63.             return 1;
64.         }
66.         int[] dp = new int[n+1];
67.         dp[1] = 1;
69.         for (int i = 2; i <= n ; i++) {
70.             dp[i] = dp[i-1] + dp[i-2];
71.         }
73.         return dp[n];
74.     }
76.     // 滚动数组
77.     public int fib4(int n) {
78.         if (n == 0){
79.             return 0;
80.         }
82.         if (n == 1){
83.             return 1;
84.         }
86.         int lastLast = 0;
87.         int last = 1;
89.         int cur = 0;
90.         for (int i = 2; i <= n; i++) {
91.             cur = last + lastLast;
92.             lastLast = last;
93.             last = cur;
94.         }
96.         return cur;
97.     }
98. }

复制代码

2. 983. 最低票价

2.1 思绪

递归

1. days [3                4                9                20                50        ...        ]
2.       0                1                2                3                4
4. costs [a                b                c]
5.        0                1                2

复制代码

递归函数 f(days,costs,i) 。该函数返回的是从days数组 索引i 的日期开始观光，所需的最小耗费。（days 和 costs 是稳固的，以下用 f(i) 代指递归函数）
i = 0，days = 3。从第三天开始观光，有下面三种方案。

1. 1. 买为期 1 天的通行证(a元)    + f(1)
2. 1. 买为期 7 天的通行证(b元)    + f(3)
3. 1. 买为期 30 天的通行证(c元)   + f(4)

复制代码

如果选择方案1，f(0) = a + f(1)。f(1) 又可以选择三种方案，就如许递归遍历下去了。不绝记载递归过程中的最小值即可。
如果选择方案2，f(0) = b + f(3)。f(3) 继续递归。
如果选择方案3，f(0) = c + f(4)。f(4) 继续递归。

影象化搜刮

1. days [3                4                9                20                50        ...        ]
2.       0                1                2                3                4
4. costs [a                b                c]
5.        0                1                2

复制代码

上面的递归方法会存在重复盘算。
days[0]、days[1]、days[2]、days[3] 都买1天车票，代价 = 4a + f(4)。
days[0] 买7天车票，days[3] 买1天车票，代价 = b + a + f(4)。
days[0] 买30天车票，代价 = c + f(4)。
以上三种情况都重复盘算了 f(4)。
用缓存数组记载效果即可。

自底向顶的动态规划

我们想知道从 days[0] 出发的最低费用，须要依赖反面days索引的返回值。
如果要从简单状态填到复杂状态，应该是从后向前的序次。
days数组的长度为n。
f(n) = 0。由于n索引越界，没有观光，也就没有费用，直接返回0。即dp[n] = 0。
dp[n-1] 依赖 dp[n]，dp[n-2] 依赖 dp[n-1] 和 dp[n]。
由此，不绝向前推，能推到dp[0]。而dp[0] 就是从days[0] 出发的最低费用。
2.2 代码

1. import java.util.Arrays;
3. /**
4. * @Title: MincostTickets
5. * @Author Wood
6. * @Package leetcode.DynamicProgramming.class66.lc983
7. * @Date 2025/4/8 19:14
8. * @description: https://leetcode.cn/problems/minimum-cost-for-tickets/
9. */
10. public class MincostTickets {
11.     // 每种方案能管几天
12.     public static int[] durations = {1,7,30};
14.     //递归
15.     public static int mincostTickets1(int[] days, int[] costs) {
16.         return f1(days,costs,0);
17.     }
19.     //递归
20.     private static int f1(int[] days, int[] costs, int i) {
21.         if (i == days.length){
22.             // 后续没有旅行了，也就没有花费
23.             return 0;
24.         }
26.         int ans = Integer.MAX_VALUE;
27.         // k 是方案编号
28.         for (int k = 0, j = i; k < 3; k++) {
29.             // j是你当前选了方案之后，方案能管到的下一天的days索引
30.             // days[i] 是出发旅行的日期
31.             // durations[k] 表示你选中的该方案的车票能管几天
32.             // days[i] + durations[k] 表示车票能管到第几天
33.             // days[j] 是车票能管到的最后一天的下一天
34.             // 下一次递归遍历从索引j开始，即f1(days,costs,j)
35.             while (j < days.length && days[i] + durations[k] > days[j]){
36.                 j++;
37.             }
39.             ans = Math.min(ans,costs[k] + f1(days,costs,j));
40.         }
41.         return ans;
42.     }
44.     // 记忆化
45.     public static int mincostTickets2(int[] days, int[] costs) {
46.         int[] dp = new int[days.length];
47.         Arrays.fill(dp, Integer.MAX_VALUE);
48.         return f2(days,costs,0,dp);
49.     }
51.     // 记忆化
52.     private static int f2(int[] days, int[] costs, int i,int[] dp) {
53.         if (i == days.length){
54.             // 后续没有旅行了，也就没有花费
55.             return 0;
56.         }
58.         if (dp[i] != Integer.MAX_VALUE){
59.             return dp[i];
60.         }
62.         int ans = Integer.MAX_VALUE;
63.         // k 是方案编号
64.         for (int k = 0, j = i; k < 3; k++) {
65.             while (j < days.length && days[i] + durations[k] > days[j]){
66.                 j++;
67.             }
69.             ans = Math.min(ans,costs[k] + f2(days,costs,j,dp));
70.         }
71.         dp[i] = ans;
72.         return ans;
73.     }
75.     public static int MAXN = 366;
76.     public static int[] dp = new int[MAXN];
78.     // 自底向顶的动态规划
79.     public static int mincostTickets3(int[] days, int[] costs){
80.         int n = days.length;
81.         Arrays.fill(dp,0,n+1,Integer.MAX_VALUE);
83.         dp[n] = 0;
84.         for (int i = n - 1; i >= 0; i--) {
85.             for (int k = 0,j = i; k < 3; k++) {
86.                 while (j < days.length && days[i] + durations[k] > days[j]){
87.                     j++;
88.                 }
89.                 dp[i] = Math.min(dp[i], costs[k] + dp[j]);
90.             }
91.         }
92.         return dp[0];
93.     }
94. }

复制代码

3. 91. 解码方法

3.1 思绪

递归

1. "1        1        0        6"
2. i   

复制代码

递归函数 f(char[] s,int i) ，s是字符串转换后得到的数组（不会变），该函数的返回效果是从索引i位置开始，i 及别的之后的位置可以或许返回多少种解码方式。以下直接用 f(i) 体现递归函数。
一共有三种情况：

• 索引i 的元素是0，没有办法转换，直接返回0。
  
• 将索引i 上的数字转换为字母，再调用 f(i+1)
  

​ 以上面的字符串为例，1 -> A，f(i+1)

• 将索引 i 与 i + 1上的数字转换为字母（条件是 i 与 i+1 所构成的数字 <=26），再调用 f(i+2)
  ​ 11 -> k，f(i+2)
  

影象化搜刮

i 的厘革范围是 0 ~ n。（n 是字符串长度）
那我们的dp数组就预备 n + 1 巨细的。
记载每次的返回效果。
自底向顶的动态规划

i 从 0开始，i位置的效果依赖于 i +1 与 i+2 的效果。
那我们先填n位置的效果，也就是 1。再填 n-1、n-2，从右往左推断。
滚动数组

求 i 位置 依赖 i +1 和 i+2 。
求 i -1 位置 依赖 i 和 i+1 。
如许的话每须要整一张表，直接两个变量滚动更新即可。
next 记载 i + 1 的效果。
nextNext记载 i + 2 的效果。
i 的 效果就是 next + nextNext。
下一步 nextNext 记载 i + 1 的效果。next 记载 i 的效果。就能得出 i - 1 的效果。
3.2 代码

1. import java.util.Arrays;
3. /**
4. * @Title: NumDecodings
5. * @Author Wood
6. * @Package leetcode.DynamicProgramming.class66.lc91
7. * @Date 2025/4/9 13:55
8. * @description: https://leetcode.cn/problems/decode-ways/
9. */
10. public class NumDecodings {
11.     // 递归
12.     public static int numDecodings1(String s) {
13.         return f1(s.toCharArray(),0);
14.     }
16.     // 递归
17.     private static int f1(char[] s, int i) {
18.         if (i == s.length){
19.             // 证明之前所选的方案可以形成一种有效编码
20.             return 1;
21.         }
23.         int ans;
24.         if (s[i] == '0'){
25.             ans = 0;
26.         }else {
27.             // 索引i上的数字自己转
28.             ans = f1(s,i+1);
30.             // i 和 i+1 一起转
31.             // 以 '11' 为例
32.             // (s[i] - '0') * 10 = ('1' - '0') * 10 = 1 * 10 = 10
33.             // (s[i+1] - '0') = ('1' - '0') = 1
34.             // 10 + 1 = 11
35.             if (i + 1 < s.length && (s[i] - '0') * 10 + (s[i+1] - '0') <= 26){
36.                 ans += f1(s,i+2);
37.             }
38.         }
40.         return ans;
41.     }
43.     // 记忆化搜索
44.     public static int numDecodings2(String s){
45.         int[] dp = new int[s.length()];
46.         Arrays.fill(dp,-1);
47.         return f2(s.toCharArray(),0,dp);
48.     }
50.     // 记忆化搜索
51.     private static int f2(char[] s, int i, int[] dp) {
52.         if (i == s.length){
53.             return 1;
54.         }
56.         if (dp[i] != -1){
57.             return dp[i];
58.         }
60.         int ans;
61.         if (s[i] == '0'){
62.             ans = 0;
63.         }else {
64.             ans = f2(s,i+1,dp);
66.             if (i+1 < s.length && (s[i] - '0') * 10 + (s[i+1] - '0') <= 26){
67.                 ans += f2(s,i+2,dp);
68.             }
69.         }
70.         dp[i] = ans;
71.         return ans;
72.     }
74.     // 自底向顶的动态规划
75.     public static int numDecodings3(String str){
76.         char[] s = str.toCharArray();
77.         int n = s.length;
79.         int[] dp = new int[n + 1];
80.         Arrays.fill(dp,-1);
81.         dp[n] = 1;
83.         for (int i = n-1; i >= 0; i--) {
84.             if (s[i] == '0'){
85.                 dp[i] = 0;
86.             }else {
87.                 dp[i] = dp[i+1];
89.                 if (i+1 < s.length && (s[i] - '0') * 10 + (s[i+1] - '0') <= 26){
90.                     dp[i] += dp[i+2];
91.                 }
92.             }
93.         }
94.         return dp[0];
95.     }
97.     // 滚动数组
98.     public static int numDecodings4(String s){
99.         // dp[n] = 1
100.         int next = 1;
102.         // dp[n+1]不存在
103.         int nextNext = 0;
105.         for (int i = s.length(),cur; i >= 0; i--) {
106.             if (s.charAt(i) == '0'){
107.                 cur = 0;
108.             }else {
109.                 cur = next;
111.                 if (i+1 < s.length() && (s.charAt(i) - '0') * 10 + (s.charAt(i+1) - '0') <= 26){
112.                     cur += nextNext;
113.                 }
114.             }
115.             nextNext = next;
116.             next = cur;
117.         }
118.         return next;
119.     }
120. }

复制代码

4. 639. 解码方法 II

4.1 思绪

递归

• 如果 i 位置是0，没办法转，直接返回0。
  
• i 位置 不是0 （i 位置的字符单独转，f(i+1)后续能有多少种转换情况）
  

• i 位置不是 ‘*’ ，那么 i 上的数字就是 1 ~ 9 ，继续递归调用 f(i+1)
  
• i 位置是 ‘*’ ，而 ‘*’ 可以转换 1 ~ 9，那效果就是 9 * f(i+1)
  

• i 和 i +1 一起转 （f(i + 2) 后续有多少种转换情况）
  
  
  
  • i 和 i +1 都是数字
    
    
    
    • 如果它们合起来的数字<= 26，继续调用f(i + 2) 。否则返回0
      
    
    
  • i 是数字， i +1 是 ‘*’
    
    
    
    • i 是 1， i +1 是 ‘*’ ，效果 9 * f(i + 2)。（从11到19，统共是9种情况）
      
    • i 是 2， i +1 是 ‘*’ ，效果 6 * f(i + 2)。（从21到26，统共是6种情况）
      
    • i位置的数字 > 2，直接返回0。
      
    
    
  • i 是**‘*’**， i +1 是 数字
    
    
    
    • i 是**‘‘， i +1 是 6，效果 2 * f(i + 2)。（’’** 只能是1，2）
      
    • i 是**‘‘， i +1 > 6，效果 1 * f(i + 2)。（’’** 只能是1）
      
    
    
  • i 是 ‘*’， i +1 是 ‘*’
    
  • 效果 15 * f(i + 2)。（从11 ~ 19，以及 21 ~ 26 ，统共15种情况）
    
  
  

4.2 代码

1. import java.util.Arrays;
3. /**
4. * @Title: NumDecodingsII
5. * @Author Wood
6. * @Package leetcode.DynamicProgramming.class66.lc639
7. * @Date 2025/4/9 15:38
8. * @description: https://leetcode.cn/problems/decode-ways-ii/
9. */
10. public class NumDecodingsII {
11.     public static int MOD = 1000000007;
13.     // 递归
14.     public static int numDecodings1(String s) {
15.         return f1(s.toCharArray(),0);
16.     }
18.     // 递归
19.     private static int f1(char[] s, int i) {
20.         if (i == s.length){
21.             return 1;
22.         }
24.         if (s[i] == '0'){
25.             return 0;
26.         }
28.         // s[i] != '0'
29.         // 2) i想单独转
30.         int ans = f1(s,i+1) * (s[i] == '*' ? 9 : 1);
32.         // 3) i i+1 一起转
33.         if (i + 1 < s.length){
34.             if (s[i] != '*'){
35.                 if (s[i+1] != '*'){
36.                     // num  num
37.                     //  i   i+1
38.                     if ((s[i] - '0') * 10 + (s[i+1] - '0') <= 26){
39.                         ans += f1(s,i+2);
40.                     }
41.                 }else {
42.                     // num  *
43.                     //  i  i+1
44.                     if (s[i] == '1'){
45.                         ans += f1(s,i+2) * 9;
46.                     }
48.                     if (s[i] == '2'){
49.                         ans += f1(s,i+2) * 6;
50.                     }
51.                 }
52.             }else {
53.                 if (s[i+1] != '*'){
54.                     // *  num
55.                     // i  i+1
56.                     if (s[i+1] <= '6'){
57.                         ans += f1(s,i+2) * 2;
58.                     }else {
59.                         ans += f1(s,i+2);
60.                     }
61.                 }else {
62.                     // *  *
63.                     // i  i+1
64.                     ans += f1(s,i+2) * 15;
65.                 }
66.             }
67.         }
69.         return ans % MOD;
70.     }
72.     // 记忆化
73.     public static int numDecodings2(String str){
74.         char[] s = str.toCharArray();
75.         long[] dp = new long[s.length];
76.         Arrays.fill(dp,-1);
77.         return (int) f2(s,0,dp);
78.     }
80.     // 记忆化
81.     private static long f2(char[] s, int i, long[] dp) {
82.         if (i == s.length){
83.             return 1;
84.         }
86.         if (s[i] == '0'){
87.             return 0;
88.         }
90.         if (dp[i] != -1){
91.             return (int) dp[i];
92.         }
94.         long ans = f2(s,i+1,dp) * (s[i] == '*' ? 9 : 1);
96.         // 3) i i+1 一起转
97.         if (i + 1 < s.length){
98.             if (s[i] != '*'){
99.                 if (s[i+1] != '*'){
100.                     // num  num
101.                     //  i   i+1
102.                     if ((s[i] - '0') * 10 + (s[i+1] - '0') <= 26){
103.                         ans += f2(s,i+2,dp);
104.                     }
105.                 }else {
106.                     // num  *
107.                     //  i  i+1
108.                     if (s[i] == '1'){
109.                         ans += f2(s,i+2,dp) * 9;
110.                     }
112.                     if (s[i] == '2'){
113.                         ans += f2(s,i+2,dp) * 6;
114.                     }
115.                 }
116.             }else {
117.                 if (s[i+1] != '*'){
118.                     // *  num
119.                     // i  i+1
120.                     if (s[i+1] <= '6'){
121.                         ans += f2(s,i+2,dp) * 2;
122.                     }else {
123.                         ans += f2(s,i+2,dp);
124.                     }
125.                 }else {
126.                     // *  *
127.                     // i  i+1
128.                     ans += f2(s,i+2,dp) * 15;
129.                 }
130.             }
131.         }
133.         ans %= MOD;
134.         dp[i] = ans;
136.         return ans;
137.     }
139.     // 自底向顶的动态规划
140.     public static int numDecodings3(String str){
141.         char[] s = str.toCharArray();
142.         int n = s.length;
143.         long[] dp = new long[n+1];
144.         dp[n] = 1;
146.         for (int i = n-1; i >= 0; i--) {
147.             if (s[i] != '0'){
148.                 dp[i] = dp[i+1]  * (s[i] == '*' ? 9 : 1);
150.                 if (i + 1 < n) {
151.                     if (s[i] != '*') {
152.                         if (s[i + 1] != '*') {
153.                             // num  num
154.                             //  i   i+1
155.                             if ((s[i] - '0') * 10 + (s[i + 1] - '0') <= 26) {
156.                                 dp[i] += dp[i + 2];
157.                             }
158.                         } else {
159.                             // num  *
160.                             //  i  i+1
161.                             if (s[i] == '1') {
162.                                 dp[i] += dp[i + 2] * 9;
163.                             }
165.                             if (s[i] == '2') {
166.                                 dp[i] += dp[i + 2] * 6;
167.                             }
168.                         }
169.                     } else {
170.                         if (s[i + 1] != '*') {
171.                             // *  num
172.                             // i  i+1
173.                             if (s[i + 1] <= '6') {
174.                                 dp[i] += dp[i + 2] * 2;
175.                             } else {
176.                                 dp[i] += dp[i + 2];
177.                             }
178.                         } else {
179.                             // *  *
180.                             // i  i+1
181.                             dp[i] += dp[i + 2] * 15;
182.                         }
183.                     }
184.                 }
185.                 dp[i] %= MOD;
186.             }
187.         }
188.         return (int) dp[0];
189.     }
191.     // 空间压缩
192.     public static int numDecodings4(String str){
193.         char[] s = str.toCharArray();
194.         int n = s.length;
195.         long cur = 0, next = 1, nextNext = 0;
197.         for (int i = n-1; i >= 0 ; i--) {
198.             if (s[i] != '0') {
199.                 cur = next * (s[i] == '*' ? 9 : 1);
201.                 if (i + 1 < n) {
202.                     if (s[i] != '*') {
203.                         if (s[i + 1] != '*') {
204.                             // num  num
205.                             //  i   i+1
206.                             if ((s[i] - '0') * 10 + (s[i + 1] - '0') <= 26) {
207.                                 cur += nextNext;
208.                             }
209.                         } else {
210.                             // num  *
211.                             //  i  i+1
212.                             if (s[i] == '1') {
213.                                 cur += nextNext * 9;
214.                             }
216.                             if (s[i] == '2') {
217.                                 cur += nextNext * 6;
218.                             }
219.                         }
220.                     } else {
221.                         if (s[i + 1] != '*') {
222.                             // *  num
223.                             // i  i+1
224.                             if (s[i + 1] <= '6') {
225.                                 cur += nextNext * 2;
226.                             } else {
227.                                 cur += nextNext;
228.                             }
229.                         } else {
230.                             // *  *
231.                             // i  i+1
232.                             cur += nextNext * 15;
233.                         }
234.                     }
235.                 }
236.                 cur %= MOD;
237.             }
239.             nextNext = next;
240.             next = cur;
241.             cur = 0;
242.         }
244.         return (int) next;
245.     }
246. }

复制代码

5. 264. 丑数 II

5.1 思绪

最暴力直接的方法就是从1开始，对每一个数字判断其的质因子是否是2、3、5。
对于遍历每一个数字，我们可以实行求出下一个丑数是多少。
从1开始，分别乘以2、3、5，得2、3、5，此中最小的是2。则下一个丑数是2。
2 分别乘以2、3、5，得4、6、10，包罗之前的乘法得出的效果，最小的是3。
3 分别乘以2、3、5，得6、9、15，包罗之前的乘法得出的效果，最小的是4。

在此根本上我们可以改进。

预备三个指针，* 2、* 3、 * 5。它们最初都指向1。
1* 2 = 2、1 * 3 = 3、1 * 5 = 5。
2 最小，因此下一个丑数是2。然后 * 2指针向后移动。

上面三个指针所盘算出来的数字，3最小，下一个丑数是3。* 3指针向后移动。

下一个丑数是4，* 2指针向后移动。

下一个丑数是5，* 5指针向后移动。

下一个丑数是6，* 2、* 3指针都向后移动。

5.2 代码

1. /**
2. * @Title: NthUglyNumber
3. * @Author Wood
4. * @Package leetcode.DynamicProgramming.class66.lc264
5. * @Date 2025/4/9 17:14
6. * @description: https://leetcode.cn/problems/ugly-number-ii/
7. */
8. public class NthUglyNumber {
9.     public int nthUglyNumber(int n) {
10.          int[] dp = new int[n+1];
11.          dp[1] = 1;
13.         for (int i = 2,i2 = 1,i3 = 1, i5 = 1; i <= n; i++) {
14.             int a = dp[i2] * 2;
15.             int b = dp[i3] * 3;
16.             int c = dp[i5] * 5;
18.             int cur = Math.min(a,Math.min(b,c));
20.             if (cur == a){
21.                 i2++;
22.             }
24.             if (cur == b){
25.                 i3++;
26.             }
28.             if (cur == c){
29.                 i5++;
30.             }
32.             dp[i] = cur;
33.         }
35.         return dp[n];
36.     }
37. }

复制代码

6. 32. 最长有效括号

6.1 思绪

i 从字符串的索引0开始，从 i 位置 往左看，其有效的括号长度。
i = 0，是左括号，长度为0。
i = 1，是右括号，向左看能形成一个有效括号，长度为2。
i = 2，是右括号，但其左边还是个右括号，长度为0。
i = 3，是左括号，长度为0。
i = 4，是右括号，向左看能形成一个有效括号，长度为2。
i = 5，是左括号，长度为0。
i = 6，是右括号，向左看能形成两个有效括号，长度为4。
以此类推，返回最长长度4。

动态规划的寄义也就出来了，dp 代表子串以 i 位置末了，往左最多推多远能团体有效。
我们按照上面的流程求出dp表中每个位置的答案，然后再求dp表中的max，这个就是效果。

我们求 dp 的时间，证实 i 之前的位置，都得出效果了。
如果 i 位置是左括号，直接返回0即可。dp 之前的数值有跟没有都无所。

i 位置是右括号的话，看 dp[i-1] = 4。证实 i - 4 到 i - 1 都是有效括号。
看 i - 5 位置，如果 i - 5 上是右括号，阐明不能配对，dp = 0。

如果 i - 5 上是右括号，阐明可以配对，dp 至少是 6。即dp[i-1] + 2 = 4 + 2 = 6。
为什么说至少是6？由于我们现在并不清楚 dp[i-6] 是多少。

如果dp[i - 6] = 4，那么dp = 10。
这个时间不消再往i - 9前看了，由于dp[i-6] 就是 i - 6 往左最多推多远能团体有效的数值。
过程详解

索引0 与 索引 1都是左括号，dp[0] = 0，dp[1] = 0。
i = 2时，是右括号。dp[i-1] = 0。那么p位置就是 i位置往前跳0个，再跳1个，即 p = 1。而p位置是左括号，相称于中了图上 2 -> b分支。
那么dp = dp[2] = dp[i-1] + 2 + dp[p-1] = 0 + 2 + 0 = 2。

i = 3，是左括号，dp[3] = 0。
i = 4，是右括号，dp[i-1] = dp[3] = 0，p位置 是 i位置往前跳0个，再跳1个，即 p = 3。
p 位置是 左括号，满足2 -> b分支。
dp[4] = dp[i-1] + 2 + dp[p-1] = 0 + 2 + 2 = 4。

i = 5，是右括号。
dp[i-1] = 4，p = 0。p 是 左括号，满足 2 -> b分支。
dp[5] = dp[i-1] + 2 + dp[p-1] = dp[4] + 2 + dp[-1] = 4 + 2 + 0 = 6。
p - 1 = -1 不存在，以是dp[-1] 直接返回0。

6.2 代码

1. /**
2. * @Title: LongestValidParentheses
3. * @Author Wood
4. * @Package leetcode.DynamicProgramming.class66.lc32
5. * @Date 2025/4/9 19:30
6. * @description: https://leetcode.cn/problems/longest-valid-parentheses/
7. */
8. public class LongestValidParentheses {
9.     public int longestValidParentheses(String str) {
10.         char[] s = str.toCharArray();
11.         int[] dp = new int[s.length];
13.         int ans = 0;
14.         for (int i = 1,p; i < s.length; i++) {
15.             if (s[i] == ')'){
16.                 p = i - dp[i-1] - 1;
18.                 if (p >= 0 && s[p] == '('){
19.                     dp[i] = dp[i-1] + 2 + (p-1>=0 ? dp[p-1] : 0);
20.                 }
21.             }
22.             ans = Math.max(ans,dp[i]);
23.         }
25.         return ans;
26.     }
27. }

复制代码

7. 467. 围绕字符串中唯一的子字符串

7.1 思绪

1. s:                 "zabpxyzab"
2.    
3. base:        "ab...xyzabcd"       

复制代码

以 ‘a’ 末了的 s 的子串，在base中出现的最宗子串：‘xyza’ ，长度为4。（不消再看 ‘za’ 了，长度长的肯定包罗长度短的）
以 ‘b’ 末了：‘xyzab’ 长度为5
以 ‘p’ 末了：‘p’ 长度为1
以 ‘z’ 末了：‘xyz’ 长度为3
以 ‘y’ 末了：‘xy’ 长度为2
以 ‘x’ 末了：‘x’ 长度为1
最大长度是用往复重的。每个长度累加的效果就是返回值。
具体利用

s 的 0位置 是 ‘z’， z 向左不能延伸，len = 1 。dp[‘z’] = 1。
len代表当前字符能向左延伸的最长长度，dp记载的是每个字符向左延伸的最长长度。

1位置是 ‘a’，a 前面是 z ，以 a 末了子串向左延伸的最长长度为2，len = 2，dp[‘a’] = 2。

2位置是 ‘b’，b 前面是 a ，以 b 末了子串向左延伸的最长长度为3，len = 3，dp[‘b’] = 3。

3位置是 ‘p’，p 前面是 b ，而在base串中p 前面不应该是 b。以 p 末了子串向左延伸的最长长度为1，len = 1，dp[‘p’] = 1。

4 位置是 ‘x’，len = 1，dp[‘p’] = 1。

5 位置是 ‘y’，len = 2，dp[‘y’] = 2。

6 位置是 ‘z’， ‘z’ 前面是**‘y’**，我们可以复用dp[‘y’]的结论。len =dp[‘y’] + 1 = 2 + 1 = 3，dp[‘z’] = 3。

7 位置是 ‘a’， ‘a’ 前面是**‘z’**，我们可以复用dp[‘z’]的结论。len =dp[‘z’] + 1 = 3 + 1 = 4，dp[‘a’] = 4。

8 位置是 ‘b’， ‘b’ 前面是**‘a’**，我们可以复用dp[‘a’]的结论。len =dp[‘a’] + 1 = 4 + 1 = 5，dp[‘b’] = 5。

7.2 代码

1. public int findSubstringInWraproundString(String str) {
2.     int n = str.length();
3.     int[] s = new int[n];
4.     for (int i = 0; i < n; i++) {
5.         s[i] = str.charAt(i) - 'a'; // 将字符转换成数字
6.     }
8.     // 记录26个字母中以每个字符作结尾延伸的最长长度
9.     int[] dp = new int[26];
10.     // 第一个字符的长度初始值一定为1
11.     dp[s[0]] = 1;
13.     for (int i = 1,cur,pre,len = 1; i < n; i++) {
14.         cur = s[i];
15.         pre = s[i-1];
17.         if ((pre == 25 && cur == 0) || pre + 1 == cur){
18.             len++;
19.         }else {
20.             len = 1;
21.         }
23.         dp[cur] = Math.max(dp[cur],len);
24.     }
26.     int ans = 0;
27.     for (int i = 0; i < 26; i++) {
28.         ans += dp[i];
29.     }
30.     return ans;
31. }

复制代码

8. 940. 差别的子序列 II

8.1 思绪

0位置是a，我们的利用是 生存之前的子序列，并将 a 加到之前的子序列反面。
之前的子序列是空集，以是 0 位置的子序列为 {}、{a}
以 ‘a’ 为末了的子序列数目 = 1。
all = 2（ {}、{a}）

1位置是b，生存之前的子序列，并将 b 加到之前的子序列反面。
以是 1 位置的子序列为 {}、{a}、{b}、{a，b}
以 ‘b’ 为末了的子序列数目 = 2。
all = 4

表明一下右上角的规则（看本次修改前的记载）：
纯新增的字符 = all - 当前字符(‘b’) 前次的记载 = 2 - 0 = 2。（纯新增的字符是**{b}、{a，b}**）
当前字符的记载（也就是b的记载） = 之前的记载 + 纯新增的字符 = 0 + 2 = 2
all 之前是2，加上新增字符个数，all = 2 + 2 = 4

2位置是’a’，按照之前的利用，我们可以看到{a} 重复了。
按照右上角的规则：
纯新增的字符 = all - 当前字符前次的记载（a） = 4 - 1 = 3
以是新增了3个

更改当前字符记载（a） = 1 + 3 = 4
all = 4 + 3 = 7

8.2 代码

1. public int distinctSubseqII(String str) {
2.     int mod = 1000000007;
3.     char[] s = str.toCharArray();
4.     // 记录a-z中为结尾字符的子序列数量
5.     int[] cnt = new int[26];
6.     int all = 1,newAdd = 0;
8.     for (char c : s) {
9.         newAdd = (all - cnt[c - 'a'] + mod) % mod;
10.         cnt[c-'a'] = (cnt[c-'a'] + newAdd) % mod;
11.         all = (all + newAdd) % mod;
12.     }
13.     return (all -1 + mod) % mod;
14. }

复制代码

284605611)]
0位置是a，我们的利用是 生存之前的子序列，并将 a 加到之前的子序列反面。
之前的子序列是空集，以是 0 位置的子序列为 {}、{a}
以 ‘a’ 为末了的子序列数目 = 1。
all = 2（ {}、{a}）

[外链图片转存中…(img-aqx2hv6r-1744284605611)]
1位置是b，生存之前的子序列，并将 b 加到之前的子序列反面。
以是 1 位置的子序列为 {}、{a}、{b}、{a，b}
以 ‘b’ 为末了的子序列数目 = 2。
all = 4

表明一下右上角的规则（看本次修改前的记载）：
纯新增的字符 = all - 当前字符(‘b’) 前次的记载 = 2 - 0 = 2。（纯新增的字符是**{b}、{a，b}**）
当前字符的记载（也就是b的记载） = 之前的记载 + 纯新增的字符 = 0 + 2 = 2
all 之前是2，加上新增字符个数，all = 2 + 2 = 4

[外链图片转存中…(img-2TL3sQAi-1744284605611)]
2位置是’a’，按照之前的利用，我们可以看到{a} 重复了。
按照右上角的规则：
纯新增的字符 = all - 当前字符前次的记载（a） = 4 - 1 = 3
以是新增了3个

[外链图片转存中…(img-G9wJXr7K-1744284605611)]
更改当前字符记载（a） = 1 + 3 = 4
all = 4 + 3 = 7

[外链图片转存中…(img-y0tSvpOM-1744284605611)]

[外链图片转存中…(img-Ttc4FFnN-1744284605611)]
8.2 代码

1. public int distinctSubseqII(String str) {
2.     int mod = 1000000007;
3.     char[] s = str.toCharArray();
4.     // 记录a-z中为结尾字符的子序列数量
5.     int[] cnt = new int[26];
6.     int all = 1,newAdd = 0;
8.     for (char c : s) {
9.         newAdd = (all - cnt[c - 'a'] + mod) % mod;
10.         cnt[c-'a'] = (cnt[c-'a'] + newAdd) % mod;
11.         all = (all + newAdd) % mod;
12.     }
13.     return (all -1 + mod) % mod;
14. }

复制代码