[Algorithm][动态规划][回文串问题][分割回文串 II][最长回文子序列][让字符串成为回文串的最少插入次数]详细讲解

1.分割回文串 II

1.题目链接

• 分割回文串 II

2.算法原理详解

• 思路：

  • 确定状态表示 -> dp[i]的含义

    • 子串s[0][i]，最少分割次数

  • 推导状态转移方程
    

  • 优化：按回文子串逻辑，将字符串内的所有字串是否是回文先判断出来

  • 初始化：vector<int> dp(n, INT_MAX)

  • 确定填表顺序：从左往右

  • 确定返回值：dp[n - 1]

3.代码实现

int minCut(string s) 
{
    int n = s.size();

    // 预处理
    vector<vector<bool>> isPal(n, vector<bool>(n));
    for(int i = n - 1; i >= 0; i--)
    {
        for(int j = i; j < n; j++)
        {
            if(s[i] == s[j])
            {
                isPal[i][j] = i + 1 < j ? isPal[i + 1][j - 1] : true;
            }
        }
    }

    // DP
    vector<int> dp(n, INT_MAX);
    for(int i = 0; i < n; i++)
    {
        if(isPal[0][i])
        {
            dp[i] = 0;
        }
        else
        {
            for(int j = 1; j <= i; j++)
            {
                if(isPal[j][i])
                {
                    dp[i] = min(dp[j - 1] + 1, dp[i]);
                }
            }
        }
    }

    return dp[n - 1];
}

2.最长回文子序列

1.题目链接

• 最长回文子序列

2.算法原理详解

• 思路：

  • 确定状态表示 -> dp[i]的含义

    • s字符串[i, j]区间内的所有的子序列，最长的回文子序列的长度(i <= j)

  • 推导状态转移方程
    

  • 初始化：不用初始化

  • 确定填表顺序：从下往上，从左往右

  • 确定返回值：dp[0][n - 1]

3.代码实现

int longestPalindromeSubseq(string s) 
{
    int n = s.size();
    vector<vector<int>> dp(n, vector<int>(n));

    for(int i = n - 1; i >= 0; i--)
    {
        dp[i][i] = 1;
        for(int j = i + 1; j < n; j++)
        {
            if(s[i] == s[j])
            {
                dp[i][j] = dp[i + 1][j - 1] + 2;
            }
            else
            {
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }

    return dp[0][n - 1];
}

3.让字符串成为回文串的最少插入次数

1.题目链接

• 让字符串成为回文串的最少插入次数

2.算法原理详解

• 思路：

  • 确定状态表示 -> dp[i]的含义

    • s字符串[i, j]区间内的子串，使它成为回文串的最小插入次数(i <= j)

  • 推导状态转移方程
    

  • 初始化：不用初始化

  • 确定填表顺序：从下往上，从左往右

  • 确定返回值：dp[0][n - 1]

3.代码实现

int minInsertions(string s) 
{
    int n = s.size();
    vector<vector<int>> dp(n, vector<int>(n));
    for(int i = n - 1; i >= 0; i--)
    {
        for(int j = i + 1; j < n; j++)
        {
            if(s[i] == s[j])
            {
                dp[i][j] = dp[i + 1][j - 1];
            }
            else
            {
                dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1;
            }
        }
    }

    return dp[0][n - 1];
}