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

这篇具有很好参考价值的文章主要介绍了【学会动态规划】环绕字符串中唯一的子字符串（25）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

动态规划怎么学？

1. 题目解析

2. 算法原理

1. 状态表示

2. 状态转移方程

3. 初始化

4. 填表顺序

5. 返回值

3. 代码编写

写在最后：

动态规划怎么学？

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

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

1. 题目解析

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

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

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

有多少不同的非空子串在 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;
    }
};