【算法篇】动态规划（二）

文章目录

• 分割回文字符串
• 编辑距离
• 不同的子序列
• 动态规划解题思路

分割回文字符串

class Solution {
public:
    bool isPal(string& s,int begin,int end)
    {
        while(begin<end)
        {
            if(s[begin]!=s[end])
            {
                return false;
            }
            begin++;
            end--;
        }
        return true;
    }
    int minCut(string s) {
        int len=s.size();
        vector<int> segsize(len+1);
        if(len==0)//空串
        {
            return 0;
        }
        if(isPal(s,0,len-1))//整体都为回文
        {
            return 0;
        }
        //进行初始化，每个字符位置的最大分割次数
        for(int i=1;i<=len;i++)
        {
            segsize[i]=i-1;
        }

        for(int i=2;i<=len;i++)
        {
            //判断0~i之间是否都为回文，因为要取的是最小值
            if(isPal(s,0,i-1))
            {
                segsize[i]=0;
            }
            //下面从j=1开始是因为上面已经将0~i-1已经判断过了
            for(int j=1;j<i;j++)
            {
                //j
                //取最小值，可能为零也可能是距离上一个回文的值加1
                if(j<i&&isPal(s,j,i-1))
                {
                    segsize[i]=min(segsize[i],segsize[j]+1);
                }
            }
        }
        return segsize[len];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

上面的时间复杂度是O(N^3)，所以为了进一步优化，就用了下面的方法用空间换取时间，下面的时间复杂度是O（N ^2）

class Solution {
public:
    vector<vector<bool>> GetMat(string & s)
    {
        int n=s.size();
        vector<vector<bool>> Mat(n,vector<bool>(n,false));
        //这里为什么是从大到小遍历，看下面的图片
        //s[i]==s[j]&&f(i+1;j-1)是回文因为要找i+1;j-1它们之间的区间，也就需要向下查找
        for(int i=n-1;i>=0;i--)
        {//这里i是小于等于j的
            for(int j=i;j<n;j++)
            {
                if(i==j)
                {
                    Mat[i][j]=true;
                }
                else if(i+1==j)
                {
                    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();
        vector<int> segsize(len+1);
        vector<vector<bool>> Mat=GetMat(s);
        if(len==0)//空串
        {
            return 0;
        }
        if(isPal(s,0,len-1))//整体都为回文
        {
            return 0;
        }
        //进行初始化，每个字符位置的最大分割次数
        for(int i=0;i<=len;i++)
        {
            segsize[i]=i-1;
        }

        for(int i=2;i<=len;i++)
        {
            //判断0~i之间是否都为回文，因为要取的是最小值
            //下面从j=1开始是因为上面已经将0~i-1已经判断过了
            for(int j=0;j<i;j++)
            {
                //j
                //取最小值，可能为零也可能是距离上一个回文的值加1
                if(Mat[j][i-1])
                {
                    segsize[i]=min(segsize[i],segsize[j]+1);
                }
            }
        }
        return segsize[len];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

编辑距离

class Solution {
public:
    int minDistance(string word1, string word2) {
        int row=word1.size();
        int col=word2.size();

        vector<vector<int>> mindis(row+1,vector<int>(col+1));
        for(int i=0;i<row+1;i++)
        {
            mindis[i][0]=i;
        }
        //[0][0]位置已经初始化过了
        for(int j=1;j<col+1;j++)
        {
            mindis[0][j]=j;
        }

        for(int i=1;i<=row;i++)
        {
            for(int j=1;j<=col;j++)
            {
                //选择插入或者删除
                mindis[i][j]=min(mindis[i-1][j],mindis[i][j-1])+1;
                //替换
                if(word1[i-1]==word2[j-1])//字符的位置与数组的位置相差一
                {//如果相等的话，就直接取mindis[i-1][j-1]，但是也是需要比较一下的
                    mindis[i][j]=min(mindis[i][j],mindis[i-1][j-1]);
                }
                else
                {//替换和插入删除进行比较，mindis[i-1][j-1]+1因为不相等所以要加一
                    mindis[i][j]=min(mindis[i][j],mindis[i-1][j-1]+1);
                }
            }
        }
        return mindis[row][col];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

不同的子序列

class Solution {
public:
    int numDistinct(string s, string t) {
        // if (s.length() < t.length()) return 0;
        // int row=s.size();
        // int col=t.size();

        // //vector> dp(row+1,vector(col+1));
        // vector> dp(row+ 1, vector(col + 1, 0));
        // dp[0][0]=1;
        // for(int i=1;i<=row;i++)
        // {
        //     dp[i][0]=1;
        //     for(int j=1;j<=col;j++)
        //     {
        //         if(s[i-1]==t[j-1])
        //         {
        //             dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
        //         }
        //         else
        //         {
        //             dp[i][j]=dp[i-1][j];
        //         }
        //     }
        // }
        // return dp[row][col];




        //下面的方法解释了空间，思想还是一样的
        if (s.length() < t.length()) return 0;
        int row=s.size();
        int col=t.size();

        //vector> dp(row+1,vector(col+1));
        vector<unsigned int> dp(row+ 1);
        dp[0]=1;
        for(int i=1;i<=row;i++)
        {
            //为什么要从大到小进行，dp[j-1]+dp[j];是要取上一行的
            //所以就导致到从后开始，如果从前开始就会导致并不是从上一行当中取值
            //而是在该行当中取值
            for(int j=col;j>0;j--)
            {
                if(s[i-1]==t[j-1])
                {
                    dp[j]=dp[j-1]+dp[j];
                }
                else
                {
                    dp[j]=dp[j];
                }
            }
        }
        return dp[col];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

数组当中类型的问题，int,long long,unsigned int

1、long long比unsigned int表示范围大 2、之所以unsigned int没问题，大概是因为编译器优化了（以下为我根据实测情况下的猜测，测试方法为，给unsigned int对象初始化一个超过上限的值，能正确打印出翻转后的值，但如果这个值非常大，则会报错）：unsigned int能接受的实际值超过它的上限，当实际值超过unsigned int上限，会自动翻转（可以理解为取模）变成一个很小的数。 3、long long则不然，因为不能翻转，累加会越来越大，直到爆炸。

动态规划解题思路

动规状态定义：
状态来源：从问题中抽象状态
抽象状态：每一个状态对应一个子问题
状态的形式可以定义很多，如何验证状态的合理性：

1、某一状态的解或者多个状态处理之后解能否对应最终问题的解
2、状态之间可以形成递推关系

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

首先尝试一维状态
一维状态的合理性不满足时，再去定义二维状态

常见问题的状态：

字符串：状态一般对应字串，状态中每次一般增加一个新的字符
矩阵：二维状态–》优化—》一维状态（有机会变为一维，并不是肯定）