网站背景怎么弄,斜杠青年seo工作室,丽水手机网站建设,公司做网站用什么主机目录
引例
其余经典OJ题
1.第一题 2.第二题 3.第三题
4.第四题 5.第五题
引例
OJ 传送门Leetcode647回文子串
画图分析#xff1a; 使用动态规划解决 原理#xff1a;能够将所有子串是否是回文的信息保存在dp表中 在使用暴力方法枚举出所有子串#xff0c;是…目录
引例
其余经典OJ题
1.第一题 2.第二题 3.第三题
4.第四题 5.第五题
引例
OJ 传送门Leetcode647回文子串
画图分析 使用动态规划解决 原理能够将所有子串是否是回文的信息保存在dp表中 在使用暴力方法枚举出所有子串是使用两指针(i,j)依次往后枚举的且满足ij 所以需要建立二维的dp表在填表时只需填上三角位置即可 1.状态表示: dp[i][j]表示字符串s的[i,j](i是起始位置j是结束位置)的这个子串是否是回文 2.状态转移方程 对于线性dp可以采用多画图的方式来分析 3.初始化 因为满足ij 并且越界的情况都已经被判断了是无需做初始化的 4.填表顺序 因为在求dp[i][j]时会用到dp[i1][j-1]的值所以填表顺序是整体从下往上每一行从左往右 5.返回值 返回dp表中true的数量 具体代码
int countSubstrings(string s) {int ns.size();vectorvectorbool dp(n,vectorbool(n));//创建dp表int ret0;for(int in-1;i0;--i)//填表{for(int ji;jn;j)//从i位置开始往后枚举{if(s[i]s[j]){dp[i][j]i1j? dp[i1][j-1]:true;}if(dp[i][j]) ret;}}return ret;//返回}
其余经典OJ题
1.第一题
OJ 传送门Leetcode5最长回文子串
画图分析 使用动态规划解决 对于本道题是计算最长的回文子串在上面的例题中已经实现了判断字符串的子串是否是回文只需在dp表中为true的位置找出最长的回文串 其余的参考上面的例题 5.返回值 在dp表中为true的位置找出最长回文串的起始位置i及长度返回子串 具体代码
string longestPalindrome(string s) {int ns.size();vectorvectorbool dp(n,vectorbool(n));int begin0,len1;for(int in-1;i0;--i){for(int ji;jn;j){if(s[i]s[j]){dp[i][j]i1j? dp[i1][j-1]:true;}if(dp[i][j] j-i1len){begini;lenj-i1;}}}return s.substr(begin,len);} 2.第二题
OJ 传送门Leetcode1745分割回文串IV
画图分析 使用动态规划来解决 对于本题是将字符串划分为三子串只要每个子串是回文串即可 这里可以两下标i,j来划分这个字符串 此时只需要根据上面例题所实现的dp表来逐步划分区间判断 具体代码: bool checkPartitioning(string s) {int ns.size();//用dp把所有的子串是否是回文预处理一下vectorvectorbool dp(n,vectorbool(n));for(int in-1;i0;--i){for(int ji;jn;j){if(s[i]s[j]){dp[i][j]i1j? dp[i1][j-1]:true;}}}//枚举所有的第二个子串的起始位置及结束位置for(int i1;in-1;i){for(int ji;jn-1;j){if(dp[0][i-1] dp[i][j] dp[j1][n-1]) return true;}}return false;} 3.第三题
OJ 传送门Leetcode132分割回文串II
画图分析 使用动态规划来解决 1.状态表示 ---经验题目要求 dp[i]表示字符串s.substr(0,i1)这个子串要分割为回文串的最少分割次数 2.状态转移方程 3.初始化 对于这里的dp表本身在填表时由于j0是不会访问越界的但题目求得是最小值 在求dp[i]min(dp[j-1]1,dp[i])时若初始化时都0时dp[i]0,是会影响求min的因此初始化为INT_MAX 4.填表顺序 ------从左往右 5.返回值-------dp[n-1] 具体代码
int minCut(string s) {//预处理一下int ns.size();vectorvectorbool IsPal(n,vectorbool(n));for(int in-1;i0;--i)for(int ji;jn;j)if(s[i]s[j])IsPal[i][j]i1j? IsPal[i1][j-1]:true;vectorint dp(n,INT_MAX); for(int i0;in;i){if(IsPal[0][i]) dp[i]0;else{for(int j1;ji;j)if(IsPal[j][i]) dp[i]min(dp[j-1]1,dp[i]);}}return dp[n-1];}
4.第四题
OJ 传送门Leetcode516最长回文子序列
画图分析: 使用动态规划解决 1.状态表示 dp[i]表示以i位置为结尾的所有子序列中最长回文子序列的长度 当使用此状态表示来求解状态转移方程时
当求解dp[i]时因为此题是子序列所以需要用到dp[i-1],dp[i-2],....,而dp表中存的只是长度当在每种结果后添加字符s[i]后并不能保证是继续是回文串因此推导不出状态转移方程
这时可以借用上面例题的方法来解决这题 状态表示 dp[i][j]表示s字符串[i,j]区间内的所有子序列最长回文子序列的长度 2.状态转移方程 3.初始化 对于本题可以不用初始化会越界的位置为ij而这些位置已经判断过了 4.填表顺序 整体从上往下每一行从左往右 5.返回值 dp[0][n-1] 具体代码:
int longestPalindromeSubseq(string s) {int ns.size();vectorvectorint dp(n,vectorint(n));for(int in-1;i0;--i){for(int ji;jn;j){if(s[i]s[j]){if(ij) dp[i][j]1;else dp[i][j]dp[i1][j-1]2;}elsedp[i][j]max(dp[i1][j],dp[i][j-1]);}}return dp[0][n-1];} 5.第五题
OJ 传送门Leetcode1312让字符串成为回文串的最少插入次数
画图分析: 使用动态规划解决 1.状态表示 根据经验题目要求 dp[i][j]表示:s字符串[i,j]区间的子串让它变为回文串的最小操作次数 2.状态转移方程---认识根据s[i]与s[j]的关系来判断 3.初始化: 4.填表顺序 整体从下往上每一行从左往右 5.返回值 dp[0][n-1] 具体代码 int minInsertions(string s) {int ns.size();vectorvectorint dp(n,vectorint(n));for(int in-1;i0;--i){for(int ji1;jn;j){if(s[i]s[j]) dp[i][j]dp[i1][j-1];else dp[i][j]min(dp[i][j-1],dp[i1][j])1;}}return dp[0][n-1];}
