做网络写手最好进那个网站,做网站网站危险吗,响应式网站怎么做,建站公司用的开源系统文章目录 1.最长回文子串2.最长回文子序列3.单词拆分4.编辑距离5. 共同点和思路6. 各个问题的思路和扩展1. 最长回文子串2. 最长回文子序列3. 单词拆分4. 编辑距离 在解答字符串动态规划的应用时#xff0c;我们需要非常注意一个问题#xff1a; 有时候我们定义 d p [ i … 文章目录 1.最长回文子串2.最长回文子序列3.单词拆分4.编辑距离5. 共同点和思路6. 各个问题的思路和扩展1. 最长回文子串2. 最长回文子序列3. 单词拆分4. 编辑距离 在解答字符串动态规划的应用时我们需要非常注意一个问题 有时候我们定义 d p [ i ] [ j ] dp[i][j] dp[i][j]表示第一个字符串的第i个字符第二个字符串的第j个字符。 d p [ 0 ] [ 0 ] dp[0][0] dp[0][0]表示两个都为空串时。 使用数组下标访问时应该这样访问第一个字符串的第i个字符word1[i - 1] 总的来说dp的定义可能和数组访问下标不一样。
if(word1[i - 1] word2[j - 1])dp[i][j] ···我们还需要这样思考为什么要使用动态规划不使用其他方法为什么动态规划可以解决
1.最长回文子串
LeetCode5.最长回文子串 一个回文串 s t r [ i ] [ j ] str[i][j] str[i][j]的子串有这样的性质 s t r [ i 1 ] [ j − 1 ] str[i1][j-1] str[i1][j−1]也是回文串。
因此我们要判断一个子串 s t r [ i ] [ j ] str[i][j] str[i][j]是否是回文串我们只需要知道其子串 s t r [ i 1 ] [ j − 1 ] str[i1][j-1] str[i1][j−1]是否是回文串即可。我们使用 d p [ i ] [ j ] dp[i][j] dp[i][j]保存该区间[i,j]是否是回文串。
这样我们就使用回文字符串常用的解题方式——从长度为1的子串开始判断是否为回文串判断完后长度加一这样每次都能保证判断时其子串都已经知道是否是回文串了。
时间复杂度 O ( n 2 ) O(n^2) O(n2)
class Solution {
public:string longestPalindrome(string s) {vectorvectorbool dp(s.size(), vectorbool(s.size(), false));//dp[i]表示以i结尾的 最长回文子串dp[0][0] true;int left 0, len 1;for(int j 1; j s.size(); j){int tmp j - 1;dp[j][j] true;if(s[tmp] s[j]) {dp[tmp][j] true;left tmp; len 2;}}for(int i 2; i s.size(); i){//距离for(int j i; j s.size(); j){int tmp j - i;if(s[j] s[tmp] ){if(dp[tmp 1][j - 1] true) {dp[tmp][j] true;left tmp; len i 1;}}}}return s.substr(left, len);}
};2.最长回文子序列
LeetCode2.最长回文子序列 与最长回文子串类似本题的区别是不要求子串严格是回文串只需要包含回文串即可。
因此我们要判断一个子串 s t r [ i ] [ j ] str[i][j] str[i][j]是否包含回文串我们只需要知道其子串 s t r [ i 1 ] [ j − 1 ] str[i1][j-1] str[i1][j−1]是否包含回文串即可。我们使用 d p [ i ] [ j ] dp[i][j] dp[i][j]保存该区间[i,j]是包含的最长回文串长度。
时间复杂度 O ( n 2 ) O(n^2) O(n2)
class Solution {
public:int longestPalindromeSubseq(string s) {int n s.length();if(n 1) return 1;vectorvectorint dp(n, vectorint(n));for(int i 0; i n; i) {dp[i][i] 1;}for(int i 1; i n; i){for(int j i; j n; j){int l j - i;char c1 s[l], c2 s[j];if(c1 c2){dp[l][j] dp[l 1][j - 1] 2;}else{dp[l][j] max(dp[l][j - 1], dp[l 1][j]);}}}return dp[0][n - 1];}
};3.单词拆分
LeetCode139. 单词拆分 这个拼接的顺序不是随便的比如 c a t s a n d catsand catsand字典为 [ c a t c a t s a n d ] [catcatsand] [catcatsand]如果先用 c a t cat cat去拼接会导致问题无解但实际上有解。
定义 d p [ i ] dp[i] dp[i]表示前 i i i个字符是否可以被拼接那么它能被拼接的话我们用字典里面的词一个一个放到末尾然后看 d p [ i − d i c t . s i z e ( ) ] dp[i - dict.size()] dp[i−dict.size()]能否被拼接就能知道 d p [ i ] dp[i] dp[i]能否被拼接了。
class Solution {
public:bool wordBreak(string s, vectorstring wordDict) {vectorbool dp(s.size() 1, false);dp[0] true;for(int i 1; i s.size(); i)for(auto str : wordDict)if(str.size() i dp[i - str.size()] true)if(s.substr(i - str.size(), str.size()) str){dp[i] true;break;}return dp[s.size()];}
};4.编辑距离
LeetCode72.编辑距离 其实动态规划问题就是思考出状态以及状态转移比如这里你想要知道 w o r d 1 word1 word1到 w o r d 2 word2 word2转换次数你就只需要知道其子串。
if(word1[i - 1] word2[j - 1]){dp[i][j] dp[i - 1][j - 1];
}else{dp[i][j] min(dp[i - 1][j], min(dp[i][j - 1], dp[i - 1][j - 1])) 1;
}class Solution {
public:int minDistance(string word1, string word2) {vectorvectorint dp(word1.size() 1, vectorint(word2.size() 1));for(int i 1; i word1.size(); i){dp[i][0] i;}for(int i 1; i word2.size(); i){dp[0][i] i;}for(int i 1; i word1.size(); i){for(int j 1; j word2.size(); j){if(word1[i - 1] word2[j - 1]){dp[i][j] dp[i - 1][j - 1];}else{dp[i][j] min(dp[i - 1][j], min(dp[i][j - 1], dp[i - 1][j - 1])) 1;}}}return dp[word1.size()][word2.size()];}
};5. 共同点和思路
这些字符串相关的动态规划问题有一些共同的特点 定义状态 使用二维数组 dp 表示两个子串之间的某种状态如是否回文、最长子序列长度、是否可以拼接、编辑距离等。 状态转移 根据问题的具体要求定义状态转移方程用子问题的解构建原问题的解。 初始化 根据问题的初始条件初始化 dp 数组的边界值。 遍历顺序 通常使用双重循环遍历所有可能的子串或子序列。
6. 各个问题的思路和扩展
1. 最长回文子串
思路
定义 dp[i][j] 表示字符串 s 从第 i 到第 j 的子串是否为回文串。如果 s[i] s[j]并且 dp[i1][j-1] 为真则 dp[i][j] 为真。初始化单个字符的子串和长度为2的子串。
扩展
可以使用中心扩展法来优化时间复杂度从每个字符和字符间隙向两边扩展检查回文。
2. 最长回文子序列
思路
定义 dp[i][j] 表示字符串 s 从第 i 到第 j 的子串中最长回文子序列的长度。如果 s[i] s[j]则 dp[i][j] dp[i1][j-1] 2。否则dp[i][j] max(dp[i1][j], dp[i][j-1])。
扩展
可以尝试空间优化将二维数组优化为一维数组。
3. 单词拆分
思路
定义 dp[i] 表示字符串 s 的前 i 个字符能否被拆分成字典中的单词。对于每个位置 i检查从 j 到 i 的子串是否在字典中并且 dp[j] 是否为真。
扩展
可以使用记忆化搜索或递归的方法来优化复杂度。
4. 编辑距离
思路
定义 dp[i][j] 表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最少操作数。如果 word1[i-1] word2[j-1]则 dp[i][j] dp[i-1][j-1]。否则dp[i][j] min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) 1。
扩展
可以尝试空间优化将二维数组优化为一维数组。可以扩展到其他字符串变换问题如最长公共子序列。
