LeetCode 剑指 Offer II 动态规划（二） 专题总结

• 📚 博客主页：⭐️这是一只小逸白的博客鸭~⭐️
• 👉 欢迎 关注❤️点赞👍收藏⭐️评论📝
• 😜 小逸白正在备战实习，经常更新面试题和LeetCode题解，欢迎志同道合的朋友互相交流~
• 💙 若有问题请指正，记得关注哦，感谢~

往期文章 ：

• LeetCode 剑指 Offer II 二分查找 专题总结
• LeetCode 剑指 Offer II 排序 专题总结
• LeetCode 剑指 Offer II 回溯(上) 专题总结
• LeetCode 剑指 Offer II 回溯(下) 专题总结
• LeetCode 剑指 Offer II 动态规划（一） 专题总结

目录

094. 最少回文分割（困难）

题目：

给定一个字符串

s

，请将

s

分割成一些子串，使每个子串都是回文串。
返回符合要求的 最少分割次数 。

示例：

输入：s = “aab”
输出：1
解释：只需一次分割就可将 s 分割成 [“aa”,“b”] 这样两个回文子串。

提示：

• 1 <= s.length <= 2000
• 仅由小写英文字母组成

思路：

切割字符串成为回文串需要若干步，如切割 “

abb

” 需要先考虑 “

a

” 再考虑 “

ab

” 最后考虑 “

abb

”，对于任何一步都面临若干个选择，如切割 “

abb

” ，最后一个 ‘

b

’ 既可以组成 “

bb

” 又可以组成 “

b

” ，答案需要返回最少的切割次数，所以该问题可以使用动态规划解决。
设

dp(i)

表示字符串 s[0] ~ s[i] 的最小回文分割次数。若存在 j <= i 使得 s[j] ~ s[i] 为回文串，那么只需要在字符串 s[0] ~ s[j - 1] 后切一次，字符串 s[j] ~ s[i] 便可组成回文串，因为字符串 s[0] ~ s[j - 1] 的最小切割次数为

dp(j - 1)

，故可得

dp(i) = dp(j - 1) + 1

。因为可能存在多个 j （起码存在 j = i 使 s[j] ~ s[i] 为单个字符为回文串），最后只需在符合要求的 j 值中取

dp(i) = min (dp[i], dp(j - 1) + 1)

即可。
整个过程需要不断寻找是否存在 j <= i 使得 s[j] ~ s[i] 为回文串，这个过程的时间复杂度为

O(n)

，所以整个算法的时间复杂度为

O(n^3)

。为了优化时间复杂度，**可以先判断所有的字符串 s[j] ~ s[i] 是否为回文，并将所有的结果保存在二维数组

isPalindrome[j][i]

内**。具体的做法就是先确定回文的中心，之后从中心开始扩散确定回文的情况。处理之后，整个算法的时间复杂度可以优化为

O(n^2)

。
完整的代码如下，时间复杂度为

O(n^2)

，空间复杂度为

O(n^2)

。

classSolution{public:intminCut(string s){int n = s.length();
        vector<vector<bool>>isPalindrome(n, vector<bool>(n,true));
        vector<int>dp(n, INT_MAX);// 动态规划确认i ~ j 是否是回文串// isPalindrome[i][j]依赖于isPalindrome[i+1][j-1],所以i从大到小,j从i后面开始从小到大for(int i = n -1; i >=0; i--){for(int j = i +1; j < n; j++){
                isPalindrome[i][j]= s[i]== s[j]&& isPalindrome[i+1][j-1];}}for(int i =0; i < n; i++){// 0~i 不用切割, 之前需要切割的话也会从i开始变成0次, dp[i] = 0if(isPalindrome[0][i]==true){
                dp[i]=0;}else{// f[i] = 0 ~ i 需要切割的最小次数,从1开始,0 ~ i已经判断过不是回文串for(int j =1; j <= i; j++){// 如果j ~ i 是回文串就判断 当前值跟前一段再分割一次的最小值if(isPalindrome[j][i]){
                        dp[i]=min(dp[i], dp[j -1]+1);}}}}return dp[n -1];}};

095. 最长公共子序列

题目：

给定两个字符串

text1

和

text2

，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回

0

。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

• 例如，"ace" 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例：

输入：text1 = “abcde”, text2 = “ace”
输出：3
解释：最长公共子序列是 “ace” ，它的长度为 3 。

提示：

• 1 <= text1.length, text2.length <= 1000
• text1 和 text2 仅由小写英文字符组成。

思路：

两个字符串可能存在多个公共子序列，题目要求计算最长公共子序列的长度，因此可以考虑使用动态规划来解决。
用函数

f(i, j)

表示字符串 s1 中下标从 0 开始到 i 的子字符串 s1[0…i] 和字符串 s2 中下标从 0 开始到 j 的子字符串 s2[0…j] 的最长公共子序列的长度。对于

f(i, j)

，如果

s1[i] == s2[j]

，那么相当于在 s1[0…i - 1] 和 s2[0…j - 1] 的最长公共子序列的后面添加一个公共字符，也就是

f(i, j) = f(i - 1, j - 1) + 1

。如果

s1[i] != s2[j]

，那么这两个字符不可能出现在 s1[0…i] 和 s2[0…j] 的公共子序列中。此时 s1[0…i] 和 s2[0…j] 的最长公共子序列是s1[0…i - 1] 和 s2[0…j] 的最长公共子序列和s1[0…i] 和 s2[0…j - 1] 的最长公共子序列中的较大值，即

f(i, j) = max(f(i - 1, j), f(i, j - 1))

。
所以转移状态方程为

s1[i] == s2[j]

时，

f(i, j) = f(i-1, j-1) + 1

s1[i] != s2[i]

时，

f(i, j) = max(f(i-1, j), f(i, j-1)

时间复杂度为

O(mn)

，空间复杂度为

O(mn)

。

classSolution{public:intlongestCommonSubsequence(string text1, string text2){int n = text1.length();int m = text2.length();
        vector<vector<int>>dp(n+1, vector<int>(m+1));for(int i =0; i <= n; i++){for(int j =0; j <= m; j++){if(i ==0|| j ==0){
                    dp[i][j]=0;continue;}if(text1[i-1]== text2[j-1]){
                    dp[i][j]= dp[i-1][j-1]+1;}else{
                    dp[i][j]=max(dp[i-1][j], dp[i][j-1]);}}}return dp[n][m];}};

096. 字符串交织

题目：

给定三个字符串

s1

、

s2

、

s3

，请判断

s3

能不能由

s1

和

s2

交织（交错） 组成。
两个字符串

s

和

t

交织 的定义与过程如下，其中每个字符串都会被分割成若干 非空 子字符串：

• s = s1 + s2 + ... + sn
• t = t1 + t2 + ... + tm
• |n - m| <= 1
• 交织 是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ...

提示：

a + b

意味着字符串

a

和

b

连接。

示例：

输入：s1 = “aabcc”, s2 = “dbbca”, s3 = “aadbbcbcac”
输出：true

提示：

• 0 <= s1.length, s2.length <= 100
• 0 <= s3.length <= 200
• s1、s2、和 s3 都由小写英文字母组成

思路：

因为每一步都需要从两个字符串中的不同位置处选择字符，所以需要使用两个变量来确定状态转移方程。设

f(i, j)

表示字符串 s1 的下标从 0 到 i 的子字符串 s1[0] ~ s1[i] （长度为

i + 1

) 和字符串 s2 的下标从 0 到 j 的子字符串 s2[0] ~ s2[j] （长度为

j + 1

) 能否交织成字符串 s3 的下标从 0 到 i + j + 1 的子字符串 s3[0] ~ s3[i + j + 1] （长度为

i + j + 2

)。
根据交织的规则，字符串 s3 下标为 i + j + 1 的字符 s3[i + j + 1] 既可能来自于字符串 s1 的下标为 i 的字符 s1[i]，也可能来自于字符串 s2 的下标为 j 的字符 s2[j]。如果

s3[i + j + 1] == s1[i]

成立，那么字符 s3[i + j + 1] 可以来自于字符串 s1，那么可以的得到 f(i, j) = f(i - 1, j)，也就是说此时只要 s1[0] ~ s1[i - 1] 和 s2[0] ~ s2[j] 可以交织成 s3[0] ~ s3[i + j]，那么 s1[0] ~ s1[i] 和 s2[0] ~ s2[j] 也可以交织成 s3[0] ~ s3[i + j + 1]。同理可得，若

s3[i + j + 1] == s2[j]

成立，那么

f(i, j) = f(i, j - 1)

。以上两个选择只要其中一个能使

f(i, j)

为 true即可。所以可得状态转移方程为

dp[i][j] = ((ch1 == ch3) && dp[i-1][j]) || ((ch2 == ch3) && dp[i][j-1]);

因为存在上式中 i, j >= 0，所以会出现· f(i, -1)· 的情况，这表示字符串 s2 的子串为空时 s1[0] ~ s1[i] 是否可以交织为 s3[0] ~ s3[i]，即两者是否相等。同理 ·f(-1, j)· 表示字符串 s1 的子串为空时 s2[0] ~ s2[j] 是否可以交织为 s3[0] ~ s3[j]，即两者是否相等。另外

f(-1, -1)

表示两个空的字符串是否可以交织成一个空的字符串，这显然成立，所以

f(-1, -1) = true

。
时间复杂度为

O(mn)

，空间复杂度为

O(mn)

。

以 s1 = “aabcc”, s2 = “dbbca”, s3 = “aadbbcbcac” 为例子，二维 DP 矩阵如下

classSolution{public:boolisInterleave(string s1, string s2, string s3){int n = s1.size(), m = s2.size();if(n + m != s3.size()){returnfalse;}
        vector<vector<bool>>dp(n+1, vector<bool>(m+1,false));
        dp[0][0]=true;for(int i =0; i < n && s1[i]== s3[i]; i++){
            dp[i +1][0]=true;}for(int j =0; j < m && s2[j]== s3[j]; j++){
            dp[0][j +1]=true;}// dp[i][j] = ((ch1 == ch3) && dp[i-1][j]) || ((ch2 == ch3) && dp[i][j-1]);for(int i =0; i < n; i++){for(int j =0; j < m; j++){char ch1 = s1[i];char ch2 = s2[j];char ch3 = s3[i + j +1];
                dp[i +1][j +1]=((ch1 == ch3)&& dp[i][j +1])||((ch2 == ch3)&& dp[i +1][j]);}}return dp[n][m];}};