太狠了吧😅
1 1

相关推荐

12-14 15:22
门头沟学院 C++
647、回文子串://动态规划解法:布尔类型的二维dp数组        //dp[i][j]:区间范围[i,j](左闭右闭)的子串是否是回文子串,如果是dp[i][j]为true,否则为false。        //递推公式:主要分为s[i]和s[j]相等和不相等的情况        //不相等时:dp[i][j] = false;        //相等时:        //1、i=j时为单个字符,所以dp[i][j] = true        //2、j-i=1时为两个相同的字符,所以dp[i][j] = true        //3、看dp[i][j]是否为true,可以由dp[i+1][j-1]推导出来        //初始化:全初始化为false,后面再去判断更新        //遍历顺序:由于dp[i][j]要由dp[i+1][j-1]推导出来,所有i从大到小,j从小到大遍历(因为是字符串区间,所以j一定要大于i)516、回文子序列://回文子序列不要求连续        //dp[i][j]:区间范围[i,j](左闭右闭)的子串的最长回文子序列        //递推公式:主要看s[i]和s[j]是否相等        //如果相等,则dp[i][j] = dp[i+1][j-1] + 2;//注意单个字符和两个字符的情况        //不相等,则dp[i][j] = max(dp[i+1][j], dp[i][j-1]);        //初始化:全初始化为0;        //遍历顺序i--,j++
点赞 评论 收藏
分享
牛客网
牛客企业服务