西山网站建设,grace6.1 wordpress,在线设计工具的网站怎么做,外贸圈是什么一:题目 二:上码
class Solution {
public:/**思路:1.分析题意 这个是让我们求最值,那么首先想到动态规划2.动态规划1:确定dp数组以及下标的含义dp[i][j] 表示字符串在[i,j]范围内的最长回文子序列2:确定dp数组的状态递推公式那么就是s[i] 与 s[j] 相等 不相等两种情况…一:题目 二:上码
class Solution {
public:/**思路:1.分析题意 这个是让我们求最值,那么首先想到动态规划2.动态规划1:确定dp数组以及下标的含义dp[i][j] 表示字符串在[i,j]范围内的最长回文子序列2:确定dp数组的状态递推公式那么就是s[i] 与 s[j] 相等 不相等两种情况s[i] ! s[j] s[i] a 左边第一个字符s[j] c 最后一个字符a b a a b c当其不相等的时候 我们可以选择加入其中一个加入s[j] dp[i][j] dp[i1][j] b a a b c加入s[i] dp[i][j] dp[i][j-1] a b a a b那我们就选其中的最大值dp[i][j] max(dp[i1][j],dp[i][j-1])s[i] s[j] dp[i][j] dp[i1][j-1] 2;dp[i][j]表示的是在[i,j]范围内的最长的字符串那么当s[i] s[j]的话, 在字符范围的 i1 和 j-1 的范围内最长的回文子序列肯定要23:确定dp数组的初始化当一个字符的时候 我们将其dp[i][j] 初始化为 1因为当dp[i][j] dp[i-1][j1] 我们是统计不到的初始化为0 因为不可能一开始就是相等的4:确定dp数组的遍历顺序根据状态递推公式 从下往上 从左往右 5:举例验证b b b a bb 1 2 3 3 4b 1 2 2 3b 1 1 2 a 1 1 b 1 */int longestPalindromeSubseq(string s) {vectorvectorint dp(s.size(),vectorint(s.size(),0));for(int i 0; i s.size(); i) dp[i][i] 1;for (int i s.size()-1; i 0; i--) {for (int j i 1; j s.size(); j) {//这里从i1开始 是因为我们的45度斜线已经都赋值为1了if(s[i] s[j]) dp[i][j] dp[i1][j-1] 2;else dp[i][j] max(dp[i1][j],dp[i][j-1]);}}return dp[0][s.size()-1];}
};
