【C++刷题】优选算法——动态规划第四辑

1. 回文子串

状态表示:
	dp[i][j]: 表示以i位置开始，j位置结尾的子串是否是回文串
状态转移方程:
	i == j: dp[i][j] = true;
	i + 1 == j && s[i] == s[j]: dp[i][j] = true;
	i + 1 < j && dp[i+1][j-1] && s[i] == s[j]: dp[i][j] = true;

int countSubstrings(string s)
{
    // 1.dp数组
    vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));

    // 2.初始化

    // 3.状态转移方程
    for(int i = s.size() - 1; i >= 0; --i)
    {
        for(int j = i; j < s.size(); ++j)
        {
            if(i == j)
            {
                dp[i][j] = true;
            }
            else if(i + 1 == j)
            {
                if(s[i] == s[j]) dp[i][j] = true;
            }
            else
            {
                if(dp[i+1][j-1] && s[i] == s[j]) dp[i][j] = true;
            }
        }
    }

    // 4.返回值
    int ret = 0;
    for(int i = s.size() - 1; i >= 0; --i)
    {
        for(int j = i; j < s.size(); ++j)
        {
            ret += dp[i][j];
        }
    }
    return ret;
}

2. 最长回文子串

状态表示:
	dp[i][j]: 表示以i位置开始，j位置结尾的子串是否是回文串
状态转移方程:
	i == j: dp[i][j] = true;
	i + 1 == j && s[i] == s[j]: dp[i][j] = true;
	i + 1 < j && dp[i+1][j-1] && s[i] == s[j]: dp[i][j] = true;

string longestPalindrome(string s) 
{
    // 1.dp数组
    vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));

    // 2.初始化

    // 3.状态转移方程
    for(int i = s.size() - 1; i >= 0; --i)
    {
        for(int j = i; j < s.size(); ++j)
        {
            if(i == j)
            {
                dp[i][j] = true;
            }
            else if(i + 1 == j)
            {
                if(s[i] == s[j]) dp[i][j] = true;
            }
            else
            {
                if(dp[i+1][j-1] && s[i] == s[j]) dp[i][j] = true;
            }
        }
    }

    // 4.返回值
    int start = -1, end = -1;
    for(int i = s.size() - 1; i >= 0; --i)
    {
        for(int j = i; j < s.size(); ++j)
        {
            if(dp[i][j] == true)
            {
                if(start == -1)
                {
                    start = i;
                    end = j;
                }
                else
                {
                    if(j - i > end - start)
                    {
                        start = i;
                        end = j;
                    }
                }
            }
        }
    }
    return s.substr(start, end - start + 1);
}

3. 分割回文串 IV

状态表示:
	dp[i][j]: 表示以i位置开始，j位置结尾的子串是否是回文串
状态转移方程:
	i == j: dp[i][j] = true;
	i + 1 == j && s[i] == s[j]: dp[i][j] = true;
	i + 1 < j && dp[i+1][j-1] && s[i] == s[j]: dp[i][j] = true;

bool checkPartitioning(string s)
{
    // 1.dp数组
    vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));

    // 2.初始化

    // 3.状态转移方程
    for(int i = s.size() - 1; i >= 0; --i)
    {
        for(int j = i; j < s.size(); ++j)
        {
            if(i == j) dp[i][j] = true;
            else if(i + 1 == j && s[i] == s[j]) dp[i][j] = true;
            else if(dp[i+1][j-1] && s[i] == s[j]) dp[i][j] = true;
        }
    }

    // 4.返回值
    for(int i = 1; i < s.size() - 1; ++i)
    {
        for(int j = i; j < s.size() - 1; ++j)
        {
            if(dp[0][i-1] && dp[i][j] && dp[j+1][s.size() - 1]) return true;
        }
    }
    return false;
}

4. 分割回文串 II

状态表示:
	dp[i]: 表示 s[0, i]这个子串区间，最少的分割次数
状态转移方程:
	dp[i] = min(dp[j-1]+1)

int minCut(string s)
{
    // 0.优化
    vector<vector<bool>> vv(s.size(), vector<bool>(s.size(), false));
    for(int i = s.size() - 1; i >= 0; --i)
    {
        for(int j = i; j < s.size(); ++j)
        {
            if(i == j) vv[i][j] = true;
            else if(i + 1 == j && s[i] == s[j]) vv[i][j] = true;
            else if(vv[i+1][j-1] && s[i] == s[j]) vv[i][j] = true;
        }
    }

    // 1.dp数组
    vector<int> dp(s.size());

    // 2.初始化

    // 3.状态转移方程
    for(int i = 0; i < dp.size(); ++i)
    {
        if(vv[0][i]) dp[i] = 0;
        else
        {
            int m = INT_MAX;
            for(int j = i; j > 0; --j)
            {
                if(vv[j][i]) m = min(m, dp[j-1] + 1);
            }
            dp[i] = m;
        }
    }
    // 4.返回值
    return dp.back();
}

5. 最长回文子序列

状态表示:
	dp[i][j]: 表示s字符串[i,j]区间内的所有子序列中，最长回文子序列的长度
状态转移方程:
	s[i] == s[j]:
		if(i == j) dp[i][j] = 1;
        else if(i + 1 == j) dp[i][j] = 2;
        else dp[i][j] = dp[i+1][j-1] + 2;
    s[i] != s[j]:
    	dp[i][j] = max(dp[i+1][j], dp[i][j-1]);

int longestPalindromeSubseq(string s)
{
    // 1.dp数组
    vector<vector<int>> dp(s.size(), vector<int>(s.size()));

    // 2.初始化

    // 3.状态转移方程
    for(int i = s.size() - 1; i >= 0; --i)
    {
        for(int j = i; j < s.size(); ++j)
        {
            if(s[i] == s[j])
            {
                if(i == j) dp[i][j] = 1;
                else if(i + 1 == j) dp[i][j] = 2;
                else dp[i][j] = dp[i+1][j-1] + 2;
            }
            else
            {
                dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
            }
        }
    }

    // 4.返回值
    return dp[0][s.size() - 1];
}

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

状态表示:
	dp[i][j]: 表示s字符串中[i,j]区间的子串，成为回文串的最小插入次数
状态转移方程:
	s[i] == s[j]:
		if(i == j || i + 1 == j) dp[i][j] = 0;
        else dp[i][j] = dp[i+1][j-1];
    s[i] != s[j]:
    dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1;

int minInsertions(string s)
{
    // 1.dp数组
    vector<vector<int>> dp(s.size(), vector<int>(s.size()));

    // 2.初始化

    // 3.状态转移方程
    for(int i = s.size(); i >= 0; --i)
    {
        for(int j = i; j < s.size(); ++j)
        {
            if(s[i] == s[j])
            {
                if(i == j || i + 1 == j) dp[i][j] = 0;
                else dp[i][j] = dp[i+1][j-1];
            }
            else
            {
                dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1;
            }
        }
    }

    // 4.状态转移方程
    return dp[0][s.size() - 1];
}