代码随想录算法训练营第四十六天|LeetCode647.回文串、LeetCode516.最长回文子序列

前言

打卡代码随想录算法训练营第49期第四十六天 ε(*′･∀･｀)зﾞ

首先十分推荐学算法的同学可以先了解一下代码随想录，可以在B站卡哥B站账号、代码随想录官方网站代码随想录了解，卡哥清晰易懂的算法教学让我直接果断关注，也十分有缘和第49期的训练营大家庭一起进步。

LeetCode647 回文子串

题目链接：647 回文子串

文章讲解：回文子串

视频讲解：卡哥讲解 —— 回文子串

本题有点难度，但也可以自己想出来。

public class Solution {
    public int CountSubstrings(string s) {
        //dp数组含义：在i - j范围内是否为回文子串
        bool[,] dp = new bool[s.Length, s.Length];
        int result = 0;
        for(int i = s.Length - 1; i >= 0; i--)
        {
            for(int j = i; j < s.Length; j++)
            {
                if(s[i] == s[j])//如果字符相等
                {
                    if(j - i <= 1)//相减<=1就是 aa 或者 a的情况可以看做回文串
                    {
                        dp[i , j] = true;
                        result++;
                    }
                    else//>1就要判断其中间是否为回文串 是就+1不是就放弃
                    {
                        if(dp[i + 1 , j - 1])
                        {
                            dp[i , j] = true;
                            result++;
                        }
                    }
                }
                else
                    dp[i , j] = false;
            }
        } 
        return result;
    }
}

LeetCode516 最长回文子序列

题目链接：516 最长回文子序列

文章讲解：最长回文子序列

视频讲解：卡哥讲解 —— 最长回文子序列

public class Solution {
    public int LongestPalindromeSubseq(string s) {
        //dp数组含义：在i - j范围内的回文子的最大长度
        int[,] dp = new int[s.Length , s.Length];
        //当i和j指针在一起的时候 回文串长度肯定为1 所以初始化为1
        for(int i = 0; i < s.Length; i++)
            dp[i , i] = 1;
        for(int i = s.Length - 1; i >= 0; i--)
        {
            for(int j = i + 1/*因为初始化已经有了i = j情况 所以这里直接i + 1即可*/; j < s.Length; j++)
            {
                if(s[i] == s[j])//相等的情况下 就看中间情况 + 2 因为可以跳过中间的元素 所以只需要知道中间最大是多少就可以了
                    dp[i , j] = dp[i + 1 , j - 1] + 2;
                else//不相等情况就找 i + 1 到 j 和 i 到 j - 1的最大值
                    dp[i , j] = Math.Max(dp[i + 1 , j] , dp[i , j - 1]);
            }
        }
        return dp[0 , s.Length - 1];    
    }
}

学完动规了，看一下动态规划总结。明天见~~~