当前位置：首页 > news >正文

【学会动态规划】环绕字符串中唯一的子字符串（25）

news 2025/9/12 13:50:26

动态规划怎么学？

1. 题目解析

2. 算法原理

1. 状态表示

2. 状态转移方程

3. 初始化

4. 填表顺序

5. 返回值

3. 代码编写

写在最后：

动态规划怎么学？

学习一个算法没有捷径，更何况是学习动态规划，

跟我一起刷动态规划算法题，一起学会动态规划！

1. 题目解析

题目链接：467. 环绕字符串中唯一的子字符串 - 力扣（LeetCode）

这道题目也很好理解，读一遍基本就理解了，就是找他给的示例中，

有多少不同的非空子串在 base 里出现，base 就是 a ~ z a ~ z 的一个无线循环。

2. 算法原理

1. 状态表示

dp[ i ] 表示以 i 位置为结尾的所有子串里面，有多少个在 base 中出现过。

2. 状态转移方程

这里就可以分成两种情况：

如果长度为1，则 dp[ i ] = 1

如果长度大于 1 ，证明 i 位置与前面的位置结合了，那么如果：

s[ i - 1 ] + 1 == s[ i ] || ( s[ i - 1 ] == 'z' && s[ i ] == 'a' )，dp[ i ] = dp[ i - 1 ]

（之前有多少种情况，现在就有多少种情况）

因为求的是所有的情况的和，所以状态转移方程就是：

dp[ i ] = 1 + s[ i - 1 ] + 1 == s[ i ] || ( s[ i - 1 ] == 'z' && s[ i ] == 'a' ) ? dp[ i ] = dp[ i - 1 ] : 0

3. 初始化

因为每个字母一定会出现，所以我们可以直接把数组初始化成 1 ，

这样我们的状态转移方程就不用多加那个 1 了。

4. 填表顺序

从左往右。

5. 返回值

因为可能会出现字母重复的情况，所以我们不能直接返回所有元素的和，

那我们该怎么去重呢？

相同字符结尾的 dp 值，我们去最大的即可，

创建一个大小为 26 的数组，里面保存相应字符结尾的最大 dp 值即可。

最后返回数组里的和即可。

3. 代码编写

class Solution {
public:int findSubstringInWraproundString(string s) {int n = s.size();vector<int> dp(n, 1);for(int i = 1; i < n; i++) {if(s[i - 1] + 1 == s[i] || (s[i - 1] == 'z' && s[i] == 'a'))dp[i] += dp[i - 1];}int hash[26] = { 0 };for(int i = 0; i < n; i++) {hash[s[i] - 'a'] = max(hash[s[i] - 'a'], dp[i]);}int sum = 0;for(auto e : hash) sum += e;return sum;}
};