东莞如何制作自己的网站,怎么做淘宝网站教程,软件开发专业是做什么的,如何同步目录wordpress647. 回文子串 题目链接/文章讲解/视频讲解#xff1a;代码随想录 1.代码展示
//647.回文子串
int countSubstrings(string s) {//step1 构建dp数组#xff0c;明确dp数组的含义#xff0c;dp[i][j]的含义是在下标为i和j区间内的字串是否为回文串vectorvectorbool代码随想录 1.代码展示
//647.回文子串
int countSubstrings(string s) {//step1 构建dp数组明确dp数组的含义dp[i][j]的含义是在下标为i和j区间内的字串是否为回文串vectorvectorbool dp(s.size(), vectorbool(s.size(), false));//step2 构建状态转移方程//当s[i] ! s[j]时此时必定不为回文子串//当s[i] s[j]时有三种情况//情况一i j此时就是本身因此必定为回文子串//情况二i 1 j此时就如aa的形式因此也是回文子串//情况三j i 1此时当dp[i 1][j - 1]为回文字串时dp[i][j]才是回文子串//step3 初始化dp数组都为false//step4 开始遍历int nResult 0;for (int i s.size() - 1; i 0; i) {for (int j i; j s.size(); j) {if (s[i] s[j]) {if (j - i 1) {nResult;dp[i][j] true;}else if (dp[i 1][j - 1]){nResult;dp[i][j] true;}}}}return nResult;
} 2.本题小节 思考本题的重点在于对于dp[i][j]的理解dp[i][j]的含义是在下标为i和j区间内的字串是否为回文串。构建状态转移方程当s[i] ! s[j]时此时必定不为回文子串当s[i] s[j]时有三种情况 情况一i j此时就是本身因此必定为回文子串 情况二i 1 j此时就如aa的形式因此也是回文子串情况三j i 1此时当dp[i 1][j - 1]为回文字串时dp[i][j]才是回文子串初始化都为false最后注意遍历顺序先下后上先左后右。 基本思路注意理解dp[i][j]的含义按照代码的思路来即可。
516.最长回文子序列 题目链接/文章讲解/视频讲解代码随想录 1.代码展示
//516.最长回文子序列
int longestPalindromeSubseq(string s) {//step1 构建dp数组dp[i][j]的含义是在[i,j]下标的范围内s的最长回文子序列vectorvectorint dp(s.size(), vectorint(s.size(), 0));//step2 状态转移方程//当s[i] s[j]dp[i][j] dp[i 1][j - 1] 2//不等时有两种情况说明同时加入s[i],s[j]不能满足情况分别加入s[i]和s[j]试试//则dp[i][j] max(dp[i][j - 1], dp[i 1][j])//step3 初始化for (int i 0; i s.size(); i) {dp[i][i] 1;}//step4 开始遍历for (int i s.size() - 1; i 0; i) {for (int j i 1; j s.size(); j) {if (s[i] s[j]) {dp[i][j] dp[i 1][j - 1] 2;}else {dp[i][j] max(dp[i][j - 1], dp[i 1][j]);}}}return dp[0][s.size() - 1];
} 2.本题小节 思考明确dp数组的含义。dp[i][j]的含义是在[i,j]下标的范围内s的最长回文子序列。状态转移方程当s[i] s[j]dp[i][j] dp[i 1][j - 1] 2不等时有两种情况说明同时加入s[i],s[j]不能满足情况分别加入s[i]和s[j]试试则dp[i][j] max(dp[i][j - 1], dp[i 1][j])初始化时对角线都为1根据dp数组可以得。遍历时先下后上先左后右。 基本思路注意dp数组的含义按照动态规划步骤来。 动态规划总结代码随想录
