day46

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++