动态规划算法OJ刷题(3)-Toy模板网

这篇具有很好参考价值的文章主要介绍了动态规划算法OJ刷题(3)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

CC19 分割回文串-ii

问题描述

给出一个字符串s，分割s使得分割出的每一个子串都是回文串。计算将字符串s分割成回文串的最小切割数。例如:给定字符串s=“aab”，返回1，因为回文分割结果[“aa”,“b”]是切割一次生成的。

解题思路

方法1：用一维数组来完成，O(N^3)

注意转移方程必须是让两个相邻状态之间一步完成。

状态方程F(i) : 到第i个字符所需要的最小分割次数
状态转移方程 : j<i && str[j+1, i]是回文串，若F(i)=0【表示从第1个字符到第i个字符是回文串】F(i, j) = min(F(j) + 1)
初始条件 : F(i) = i - 1 ==> F(1) = 0。即单个字符只需要切0次，因为单子符都为回文串，2个字符最大需要1次，3个2次…【因为状态转移方程中要取min，那么F(i)要给一个最大的分割次数i-1】
返回结果 : F(s.size())

此题i = 0是无效状态。

动态规划算法OJ刷题(3),算法刷题,算法,动态规划,c++

//时间复杂度O(N^3)
class Solution {
  public:
    /**
     *
     * @param s string字符串
     * @return int整型
     */

    bool isPal(string& str, int start, int end) {
        while (start < end) {
            if (str[start] != str[end]) {
                return false;
            }
            start++;
            end--;
        }
        return true;
    }

    int minCut(string s) {
        // write code here
        int len = s.size();
        if (0 == len) return 0;
        
        //先判断整体是不是回文串
        if (isPal(s, 0, len-1)) return 0;

        vector<int> ret(len + 1);
        //初始条件
        for (int i = 1; i <= len; ++i) {
            ret[i] = i - 1;
        }
        //状态转移方程
        for (int i = 2; i <= len; ++i) {
            //先判断整体是不是回文串
            if (isPal(s, 0, i - 1)) {
                ret[i] = 0;
                continue;
            }
            //j<i && str[j, i-1]是回文串
            for (int j = 1; j < i; ++j) {
                if (isPal(s, j, i - 1)) {
                    ret[i] = min(ret[i], ret[j] + 1);
                }
            }
        }
        return ret[len];
    }
};

方法2：用空间换时间，用二维矩阵来保存是否为回文串的状态。时间复杂度O(N^2)

状态方程F(i,j) : 区间[i, j]是否为回文串
状态转移方程 : F(i, j) : s[i]==s[j] && F(i+1, j-1) 【如果字符串的首尾相同，就缩小范围再判断】

需特殊处理：1个字符 i==j，F(i,j): true; 两个字符 i+1=j, F(i,j): s[i] == s[j]
初始条件 : i==j，F(i,j): true
返回结果 : F(s.size())

class Solution {
  public:
    /**
     *
     * @param s string字符串
     * @return int整型
     */

    bool isPal(string& str, int start, int end) {
        while (start < end) {
            if (str[start] != str[end]) {
                return false;
            }
            start++;
            end--;
        }
        return true;
    }

    vector<vector<bool>> getMat(string& s) {
        int n = s.size();
        vector<vector<bool>> Mat(n, vector<bool>(n, false));
        for (int i = n - 1; i >= 0; --i) {
            for (int j = i; j < n; j++) {
                if (j == i) Mat[i][j] = true;
                else if (j == i + 1) Mat[i][j] = (s[i] == s[j]);
                else Mat[i][j] = (s[i] == s[j] && Mat[i + 1][j - 1]);
            }
        }
        return Mat;
    }

    int minCut(string s) {
        int len = s.size();
        if (0 == len) return 0;
        //先判断整体是不是回文串
        if (isPal(s, 0, len - 1)) return 0;

        vector<vector<bool>> Mat = getMat(s);
        vector<int> ret(len + 1);
        for (int i = 0; i <= len; ++i) {
            ret[i] = i - 1;
        }

        for (int i = 2; i <= len; ++i) {
            for (int j = 0; j < i; ++j) {
                if (Mat[j][i - 1])
                    ret[i] = min(ret[i], ret[j] + 1);
            }
        }
        return ret[len];
    }
}

CC77 编辑距离

题目描述

给定两个单词word1和word2，请计算将word1转换为word2至少需要多少步操作。你可以对一个单词执行以下3种操作：a）在单词中插入一个字符；b）删除单词中的一个字符；c）替换单词中的一个字符。

就是指从1个字符串转成另一个字符串所需的最少编辑操作次数

解题思路

子问题：从word1的第i个字符到word2的第j个字符需要的操作距离

通过状态方程，可知

1、F(i, j-1)–>F(i,j)：word1[1,i]、word2[1,j-1]==>word1[1,i]==word2[1,j]，字符1的前i个字符和字符2的前j-1个字符，通过对字符2进行1次插入第j个字符操作，使得字符1的前i个字符和字符2前j个字符相等；

2、F(i-1, j) -->F(i,j)：word1[1,i-1]、word2[1,j]==>word1[1,i]==word2[1,j]，字符1的前i个字符和字符2的前j-1个字符，通过对字符1进行1次删除第i个字符的操作，使得字符1的前i个字符和字符2前j个字符相等；

3、F(i-1, j-1)–>F(i,j)：当word1[i]!=word2[j]时，才需要此操作。word1[1,i-1]、word2[1,j-1]==>word1[1,i]==word2[1,j]，通过对字符1的第i个字符进行1次替换操作，使得字符1的前i个字符和字符2前j个字符相等；

状态方程F(i,j) : 字符1前i个字符到字符2前j个字符的编辑距离
状态转移方程 : F(i, j) = min(F(i, j-1) + 1, F(i-1, j) + 1, F(i-1, j-1) + (word1[i]==word2[j]) ? 0 : 1))【1、F(i, j-1) + 1 = F(i, j); 2、F(i-1, j) + 1 = F(i, j); 3、F(i-1, j-1) + (word1[i]==word2[j]) ? 0 : 1) = F(i, j);】
初始条件 : F(i,0)=j; F(0,j)=i;
返回结果 : F[row] [col]

#include <vector>
class Solution {
  public:
    /**
     *
     * @param word1 string字符串
     * @param word2 string字符串
     * @return int整型
     */
    int minDistance(string word1, string word2) {
        // write code here
        int row = word1.size();
        int col = word2.size();

        vector<vector<int>> minD(row + 1, vector<int>(col + 1));
        //初始化
        for (int i = 0; i <= col; ++i) minD[0][i] = i;
        for (int i = 1; i <= row; ++i) minD[i][0] = i;

        for (int i = 1; i <= row; ++i) {
            for (int j = 1; j <= col; ++j) {
                //删除 删除
                minD[i][j] = min(minD[i][j - 1], minD[i - 1][j]) + 1;
                //替换
                if (word1[i - 1] == word2[j - 1]) minD[i][j] = min(minD[i][j],
                            minD[i - 1][j - 1]);
                else minD[i][j] = min(minD[i][j], minD[i - 1][j - 1] + 1);
            }
        }
        return minD[row][col];
    }
};

动态规划算法OJ刷题(3),算法刷题,算法,动态规划,c++

CC36 不同的子序列

题目描述

给定两个字符串S和T，返回S子序列等于T的不同子序列个数有多少个？字符串的子序列是由原来的字符串删除一些字符（也可以不删除）在不改变相对位置的情况下的剩余字符。例如，"ACE"是"ABCDE"的子序列，但是"AEC"不是；S=“nowcccoder”, T = “nowccoder” ，返回3【now+ccoder/nowc+coder/nowcc+oder】；S=“rabbbit”, T = “rabbit” ，返回3【ra+bbit/rab+bit/rabb+it】；

解题思路

子问题：S的前i个字符构成的子串与T的前j个字符相同的子序列的个数

子串的长度要大于等于T的长度才能找到有相同的子串。

状态方程F(i,j) : S的前i个字符已经与T的前j字符相同了
状态转移方程 :

在F(i,j)处需要考虑S[i] = T[j] 和 S[i] != T[j]两种情况:

当S[i] = T[j]: 1、让S[i]匹配T[j]，则F(i,j) = F(i-1,j-1); 2、让S[i]不匹配T[j], 则问题就变为S[1:i-1]中的子串与T[1:j]相同的个数，则F(i,j) = F(i-1,j) , 故S[i] = T[j]时，F(i,j) = F(i-1,j-1) + F(i-1,j)

当S[i] != T[j]: 问题退化为S[1:i-1]中的子串与T[1:j]相同的个数,故，S[i] != T[j]时，F(i,j) = F(i-1,j)
初始条件 : F(i,0) = 1 —> S的子串与空串相同的个数，只有空串与空串相同
返回结果 : F(S.size(), T.size())文章来源地址https://www.toymoban.com/news/detail-619590.html

class Solution {
  public:
    /**
     *
     * @param S string字符串
     * @param T string字符串
     * @return int整型
     */
    int numDistinct(string S, string T) {
        // write code here
        int s_size = S.size();
        int t_size = T.size();
        // S的长度小于T长度，不可能含有与T相同的子串
        if (S.size() < T.size()) return 0;
        // T为空串，只有空串与空串相同，S至少有一个子串，它为空串
        if (T.empty()) return 1;
        // F(i,j)，初始化所有的值为0
        vector<vector<int> > f(s_size + 1, vector<int>(t_size + 1, 0));
        // 空串与空串相同的个数为1
        f[0][0] = 1;
        for (int i = 1; i <= s_size; ++i) {
            // F(i,0)初始化
            f[i][0] = 1;
            for (int j = 1; j <= t_size; ++j) {
                // S的第i个字符与T的第j个字符相同
                if (S[i - 1] == T[j - 1]) {
                    f[i][j] = f[i - 1][j] + f[i - 1][j - 1];
                } else {
                    // S的第i个字符与T的第j个字符不相同
                    // 从S的前i-1个字符中找子串，使子串与T的前j个字符相同
                    f[i][j] = f[i - 1][j];
                }
            }
        }
        return f[s_size][t_size];
    }
};

到了这里，关于动态规划算法OJ刷题(3)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！