C++【算法】【动态规划问题】

 
class Solution {
public:
    /**
     * 
     * @param s string字符串 
     * @return int整型
     */
    bool isPal(string& s,int start,int end)
     {
         while(start
         {
             if(s[start]!=s[end])
             {
                 return false;
             }
             ++start;
             --end;
         }
         return true;
    }
    int minCut(string s) {
        // write code here
 
        int len=s.size();
        if(len==0)
            return 0;
        //判断整体是不是一个回文串
        if(isPal(s,0,len-1))
            return 0;
 
        vector<int> minCut(len+1);
        //F(i)=i-1
        //5个字符中间最多分割4次
        for(int i=1;i<=len;++i)
            minCut[i]=i-1;
        for(int i=2;i<=len;++i)
        {
            //整体是否为回文串
            if(isPal(s,0,i-1))
            {
                minCut[i]=0;
                continue;
            }
            // j
            for(int j=1;j
            {
                if(isPal(s,j,i-1))
                {
                    minCut[i]=min(minCut[i],minCut[j]+1);
                }
            }
            
        }
        return minCut[len];
    }
};

或者将0的位置也利用起来，写下面这种写法，就将整体是否为回文串和局部是否为回文串的情况归并到一起了

 
class Solution {
public:
    /**
     * 
     * @param s string字符串 
     * @return int整型
     */
    bool isPal(string& s,int start,int end)
     {
         while(start
         {
             if(s[start]!=s[end])
             {
                 return false;
             }
             ++start;
             --end;
         }
         return true;
    }
    int minCut(string s) {
        // write code here
 
        int len=s.size();
        if(len==0)
            return 0;
        if(isPal(s,0,len-1))
            return 0;
        vector<int> minCut(len+1);
        //F(i)=i-1
        for(int i=0;i<=len;++i)
            minCut[i]=i-1;
        for(int i=2;i<=len;++i)
        {
            // j
            for(int j=0;j
            {
                if(isPal(s,j,i-1))
                {
                    minCut[i]=min(minCut[i],minCut[j]+1);
                }
            }
            
        }
        return minCut[len];
    }
};

 但是上面的主代码中存在O(n^2)，并且其中调用的判断是否为回文串还有一层循环，为O(N^3)

我们可以保存这个区间是否为回文串

用一个n*n的方阵去保存下来，用空间换时间

判断回文串：

        状态F(i,j)：区间[i,j]是否为回文串

        状态转移方程：F(i,j)：s[i]==s[j] &&F(i+1,j-1)

        i==j：

                F(i,j)：true

        i+1==j：

                F(i,j)：s[i]==s[j]

初始状态：

        i==j:

        F(i,j):true

 
class Solution {
public:
    /**
     * 
     * @param s string字符串 
     * @return int整型
     */
    bool isPal(string& s,int start,int end)
     {
         while(start
         {
             if(s[start]!=s[end])
             {
                 return false;
             }
             ++start;
             --end;
         }
         return true;
    }
    vectorbool>> getMat(string & s)
    {
        int n=s.size();
        vectorbool>> Mat(n,vector<bool>(n,false));
        for(int i=n-1;i>=0;--i)
        {
            for(int j=i;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) {
        // write code here
 
        int len=s.size();
        if(len==0)
            return 0;
        if(isPal(s,0,len-1))
            return 0;
        vector<int> minCut(len+1);
        //F(i)=i-1
        vectorbool>> Mat=getMat(s);
        for(int i=0;i<=len;++i)
            minCut[i]=i-1;
        for(int i=2;i<=len;++i)
        {
            // j
            for(int j=0;j
            {
                if(Mat[j][i-1])
                {
                    minCut[i]=min(minCut[i],minCut[j]+1);
                }
            }
            
        }
        return minCut[len];
    }
};

八、编辑距离

编辑距离_牛客题霸_牛客网

描述

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

示例1

输入：

"b",""

复制返回值：

1

复制

示例2

输入：

"ab","bc"

复制返回值：

2 

 问题：word1到word2编辑距离

子问题：word1的局部变成word2局部需要的编辑距离

状态(i,j)：word1前i个字符到word2的前j个字符的编辑距离

状态转移方程：

        F(i,j)：min（插入，删除，替换）

                    min(F(i-1,j)+1,F(i,j-1)+1,F(i-1,j-1)+(w1[i]==w2[j]?0:1))

                    F(i,j-1)：（w1[1,i]-->w2[1,j-1]+插入-->F(i,j-1)+1-->F(i,j)

                    F(i-1,j)：w1[i,i-1]-->w2[1,j]+删除w1的第i个字符-->F(i-1,j)+1-->F(i,j)

                    F(i-1,j-1)：w1[1,i-1]->w2[1,j-1]+替换：w1[i]!=w2[j]-->F(i-1,j-1)+(w1[i]==w2[j]?0:1)

r:替换

i:插入

d:删除

 
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();
 
        vectorint>> minD(row+1,vector<int>(col+1));
        //初始化F(1,0):i  F(0,j):j 第一行和第一列
        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)
            {
                //插入、删除
                //插入和删除的步数中选择一个步数最小的，然后+1
                minD[i][j]=min(minD[i][j-1],minD[i-1][j])+1;
                //替换
                //如果word1的第i个就等于word2的第j个，就不需要替换
                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];
    }
};

九、不同子序列

不同的子序列_牛客题霸_牛客网

描述

给定两个字符串S和T，返回S子序列等于T的不同子序列个数有多少个？ 

字符串的子序列是由原来的字符串删除一些字符（也可以不删除）在不改变相对位置的情况下的剩余字符（例如，"ACE"is a subsequence of"ABCDE"但是"AEC"不是）
例如：

S="nowcccoder", T = "nowccoder" 

返回3 

示例1

输入：

"nowcccoder","nowccoder"

复制返回值：

3

问题：S中与T相同的子序列的个数

子问题：S的子串中与T相同的子序列的个数

状态F(i)：S的前i个字符构成的子串中与T前j个字符相同的子序列个数。

        子串的长度>=T的长度              

                        S:abaaaa            T:aba             i:4        F(i-1):1 -->aba   

                        第四个字符"a"与T的最后一个字符相同，然后取前面的字符找ab

        if(S[i]==T[j])

        :如果使用第i个字符，只能为子序列的最后一个字符，相当于和T的第j个字符匹配:F(i-1,j-1)

        :如果不使用第i个字符：F(i-1,j)

                F(i,j):

         F(i,j)：F(i-1,j-1)+F(i-1,j)

        if(S[i]!=T[j])

                ​​​​​​​肯定不能使用第i个字符

                F(i,j)=F(i-1,j)

        

初始状态F(i,0)=1（集合中寻找空集的个数）

                F(0,j)=0  (j!=0);

 
class Solution {
  public:
    /**
     *
     * @param S string字符串
     * @param T string字符串
     * @return int整型
     */
    int numDistinct(string S, string T) {
        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
        vectorint> > 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];
    }
};

由于我们这里观察到其实是要用到上一次遍历的结果，所以我们可以将二维矩阵降成一维的数组

 
class Solution {
  public:
    /**
     *
     * @param S string字符串
     * @param T string字符串
     * @return int整型
     */
    int numDistinct(string S, string T) {
        if (S.empty())
            return 0;
        if (T.empty())
            return 1;
        int len1 = S.size();
        int len2 = T.size();
        vector<int> numDis(len2 + 1, 0);
        numDis[0] = 1;
        for (int i = 1; i <= len1; ++i) {
            //从后向前更新，因为我们所需要使用的是未更新的值，也就是上一行的值
            for (int j = len2; j > 0; --j) {
                if (S[i - 1] == T[j - 1])
                    numDis[j] = numDis[j - 1] + numDis[j];
            //如果相同的话，本一次更新就等于上一次的数据
            }
        } 
        return numDis[len2];
    }
};

动态规划状态定义：

        状态来源：从问题中抽象状态

        抽象状态：每一个状态对应一个子问题

        状态的形式可以定义很多，如何验证状态的合理性：

                1.某一个状态的解或者多个状态处理之后的解能否对应最终问题的解。

                2.状态之间可以形成递推关系

        一维状态 VS 二维状态（依据问题和线索）

                首先尝试一维状态，

                一维的状态的合理性不满足的时候，再去定义二维状态。

        常见问题的状态：

                字符串：状态一般对应子串，状态中每一次一般增加一个新的字符

                矩阵：二维状态-->优化-->一维状态