C++算法之动态规划实例

动态规划解决相关问题

1.分割类型题

题目一：给定一个正整数，求其最少可以由几个完全平方数相加构成。

对于分割类型题，动态规划的状态转移方程通常并不依赖相邻的位置，而是依赖于满足分割
条件的位置。我们定义一个一维矩阵 dp，其中 dp[i] 表示数字 i 最少可以由几个完全平方数相加
构成。在本题中，位置 i 只依赖 i -k^2 的位置，如 i - 1、i - 4、i - 9 等等，才能满足完全平方分割
的条件。因此 dp[i] 可以取的最小值即为 1 + min(dp[i-1], dp[i-4], dp[i-9] · · · )。

int numSquares(int n)
{
    vector<int>dp(n+1,INT_MAX);
    dp[0]=0;
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j*j<=i;++j)
        {
            dp[i]=min(dp[i],dp[i-j*j]+1);
        }
    }
    return dp[n];
}
1
2
3
4
5
6
7
8
9
10
11
12
13

题目二：给定一个字符串和一个字符串集合，求是否存在一种分割方式，使得原字符串分割后的子字
符串都可以在集合内找到。

类似于完全平方数分割问题，这道题的分割条件由集合内的字符串决定，因此在考虑每个分
割位置时，需要遍历字符串集合，以确定当前位置是否可以成功分割。注意对于位置 0，需要初
始化值为真。

bool wordBreak(string s,vector<string>&wordDict){
    int n=s.length();
    vector<bool>dp(n+2,false);
    dp[0]=true;
    for(int i=1;i<=n;++i)
    {
        for(const string&word:wordDict)
        {
            int len=word.length();
            if(i>=len&&s.substr(i-len,len)==word)
            {
                dp[i]=dp[i]||dp[i-len];
            }
        }
    }
    return dp[n];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2.子序列问题

*题目一：给定一个未排序的整数数组，求最长的递增子序列
*
定义一个dp数组，其中dp[i]表示以i结尾的子序列的性质。
在本题中，dp[i]可以表示为以i结尾的、最长子序列长度。对于每一个位置i，如果其之前某个位置j所对应的数字小于位置i所对应的数字，则我们可以获得一个以i结尾的、长度为dp[j]+1的子序列,需要对i,j进行两层循环，时间复杂度为O(n^2).

int lengthOfLIS(vector<int>&nums)
{
    int max_length=0;
    int n=nums.size();
    for(int i=0;i<n;++i)
    {
        for(int j=0;j<i;++j)
        {
            if(nums[i]>nums[j])
            {
                dp[i]=max(dp[i],dp[j]+1);
            }
        }
        max_length=max(max_length,dp[i]);
    }
    return max_length;
}                  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

本题还可以使用二分查找将时间复杂度降低为 O(n log n)。我们定义一个 dp 数组，其中 dp[k]
存储长度为 k+1 的最长递增子序列的最后一个数字。我们遍历每一个位置 i，如果其对应的数字
大于 dp 数组中所有数字的值，那么我们把它放在 dp 数组尾部，表示最长递增子序列长度加 1；
如果我们发现这个数字在 dp 数组中比数字 a 大、比数字 b 小，则我们将 b 更新为此数字，使得
之后构成递增序列的可能性增大。以这种方式维护的 dp 数组永远是递增的，因此可以用二分查
找加速搜索。
以样例为例，对于数组 [10,9,2,5,3,7,101,18]，我们每轮的更新查找情况为：

int lengthOfLIS(vector<int>&nums)
{
    int n=nums.size();
    if(n<=1) return n;
    vector<int>dp;
    dp.push_back(num[0]);
    for(int i=1;i<n;++i)
    {
        if(dp.back()<nums[i]){
            dp.push_back(num[i]);
        }
        else{
            auto itr=lower_bound(dp.begin(),dp.end(),nums[i]);
            *itr=nums[i];
        }
    }
    return dp.size();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

题目二：最长公共子序列

对于子序列问题，第二种动态规划方法是，定义一个 dp 数组，其中 dp[i] 表示到位置 i 为止
的子序列的性质，并不必须以 i 结尾。这样 dp 数组的最后一位结果即为题目所求，不需要再对每
个位置进行统计。
在本题中，我们可以建立一个二维数组 dp，其中 dp[i][j]表示到第一个字符串位置 i 为止、到
第二个字符串位置 j 为止、最长的公共子序列长度。这样一来我们就可以很方便地分情况讨论这
两个位置对应的字母相同与不同的情况了。

int longestCommonSubsequence(string text1,string text2)
{
    int m=text1.length(),n=text2.length();
    vector<vector<int>> dp(m+1,vector<int>(n+1,0));
    for(int i=0;i<m;++i)
    {
        for(int j=1;j<=n;++j)
        {
            if(text1[i-1]==text2[j-1])
            {
                dp[i][j]=dp[i-1][j-1]+1;
            }
            else{
                dp[i][j]=max(dp[i-1][j],dp[j-1]);
            }
        }
    }
    return dp[m][n];
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

3.背包问题

背包问题是一种组合优化的 NP 完全问题：有 N 个物品和容量为 W 的背包，每个物品都有自己的体积 w 和价值 v，求拿哪些物品可以使得背包所装下物品的总价值最大。如果限定每种物品只能选择 0 个或 1 个，则问题称为 0-1 背包问题；如果不限定每种物品的数量，则问题称为无 界背包问题或完全背包问题。
我们可以用动态规划来解决背包问题。以 0-1 背包问题为例。我们可以定义一个二维数组 dp存储最大价值，其中 dp[i][j] 表示前 i 件物品体积不超过 j 的情况下能达到的最大价值。在我们遍历到第 i 件物品时，在当前背包总容量为 j 的情况下，如果我们不将物品 i 放入背包，那么 dp[i][j]= dp[i-1][j]，即前 i 个物品的最大价值等于只取前 i-1 个物品时的最大价值；如果我们将物品 i 放入背包，假设第 i 件物品体积为 w，价值为 v，那么我们得到 dp[i][j] = dp[i-1][j-w] + v。我们只需在遍历过程中对这两种情况取最大值即可，总时间复杂度和空间复杂度都为 O(NW)。

int knapsack(vector<int>weights,vector<int>values,int N,int W)
{
    vector<vector<int>> dp(N+1,vector<int>(W+1,0));
    for(int i=1;i<=N;++i)
    {
        int w=weights[i-1],v=values[i-1];
        for(int j=1;j<=W;++j)
        {
            if(j>=w)
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-w]+v);
            else 
                dp[i][j]=dp[i-1][j];
                
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

我们可以进一步对 0-1 背包进行空间优化，将空间复杂度降低为 O(W)。如图所示，假设我
们目前考虑物品 i = 2，且其体积为 w = 2，价值为 v = 3；对于背包容量 j，我们可以得到 dp[2][j]
= max(dp[1][j], dp[1][j-2] + 3)。这里可以发现我们永远只依赖于上一排 i = 1 的信息，之前算过的
其他物品都不需要再使用。因此我们可以去掉 dp 矩阵的第一个维度，在考虑物品 i 时变成 dp[j]
= max(dp[j], dp[j-w] + v)。这里要注意我们在遍历每一行的时候必须逆向遍历，这样才能够调用
上一行物品 i-1 时 dp[j-w] 的值；若按照从左往右的顺序进行正向遍历，则 dp[j-w] 的值在遍历到
j 之前就已经被更新成物品 i 的值了。

int knapsack(vector<int>weights,vector<int>values,int N,int W)
{
    vector<int> dp(W+1,0);
    for(int i=1;i<=N;++i)
    {
        int w=weight[i-1],v=values[i-1];
        for(int j=W;j>=w;--j)
        {
            dp[j]=max(dp[j],dp[j-w]+v);
        }
    }
    return dp[W];
}
1
2
3
4
5
6
7
8
9
10
11
12
13

完全背包问题：

在完全背包问题中，一个物品可以拿多次。如图上半部分所示，假设我们遍历到物品 i = 2，且其体积为 w = 2，价值为 v = 3；对于背包容量 j = 5，最多只能装下 2 个该物品。那么我们的状态转移方程就变成了 dp[2][5] = max(dp[1][5], dp[1][3] + 3, dp[1][1] + 6)。如果采用这种方法，假设背包容量无穷大而物体的体积无穷小，我们这里的比较次数也会趋近于无穷大，远超 O(NW) 的时间复杂度。
怎么解决这个问题呢？我们发现在 dp[2][3] 的时候我们其实已经考虑了 dp[1][3] 和 dp[2][1]的情况，而在时 dp[2][1] 也已经考虑了 dp[1][1] 的情况。因此，如图下半部分所示，对于拿多个物品的情况，我们只需考虑 dp[2][3] 即可，即 dp[2][5] = max(dp[1][5], dp[2][3] + 3)。这样，我们就得到了完全背包问题的状态转移方程：dp[i][j] = max(dp[i-1][j], dp[i][j-w] + v)，其与 0-1 背包问题的差别仅仅是把状态转移方程中的第二个 i-1 变成了 i。

int knapsack(vector<int>weights,vector<int>values,int N,int W)
{
    vector<vector<int>> dp(N+1,vector<int>(W+1,0));
    for(int i=1;i<=N;++i)
    {
        int w=weights[i-1],v=values[i-1];
        for(int j=1;j<=W;++j)
        {
            if(j>=w){
                dp[i][j]==max(dp[i-1][j],dp[i][j-w]+v);
            else
                dp[i][j]=dp[i-1][j];
        }
    }
    return dp[N][W];
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

同样的，我们也可以利用空间压缩将时间复杂度降低为 O(W)。这里要注意我们在遍历每一行的时候必须正向遍历，因为我们需要利用当前物品在第 j-w 列的信息。

int knapsack(vector<int>weights,vector<int>values,int N,int W)
{
    vector<int>dp(W+1,0);
    for(int i=1;i<=N;++i)
    {
        int w=weights[i-1],v=values[i-1];
        for(int j=w;j<=W;++j)
        {
            dp[j]=max([dp[j],dp[j-w]+v);
        }
    }
    return dp[W];
}
1
2
3
4
5
6
7
8
9
10
11
12
13

题目二：给定一个正整数数组，求是否可以把这个数组分成和相等的两部分。

本题等价于 0-1 背包问题，设所有数字和为 sum，我们的目标是选取一部分物品，使得它们的总和为 sum/2。这道题不需要考虑价值，因此我们只需要通过一个布尔值矩阵来表示状态转移矩阵。注意边界条件的处理。

bool canPartition(vector<int>&nums)
{
    int sum=accumulate(nums.begin(),nums.end(),0);
    if(sum%2) return false;
    int target =sum/2,n=nums.size();
    vector<vector<bool>> dp(n+1,vector<bool>(target+_1,false));
    for(int i=0;i<=n;++i)
    {
        dp[i][0]=true;
    }
    for(int i=1;i<=n;++i)
    {
        for(int j=nums[i-1];j<=target;++j){
            dp[i][j]=dp[i-1][j]||dp[i-1][jj-nums[i-1]];
        }
    }
    return dp[n][target];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

同样的，我们也可以对本题进行空间压缩。注意对数字和的遍历需要逆向。

bool canPartition(vector<int>&nums)
{
    int sum=accumulate(nums.begin(),nums.end(),0);
    if(sum%2) return false;
    int target =sum/2,n=nums.size();
    vector<bool>dp(target+1,false);
    dp[0]=true;
    for(int i=1;i<=n;++i)
    {
        for(int j=target;j>=nums[i-1];--j)
        {
            dp[j]=dp[j]||dp[j-nums[i-1]];
        }
    }
    return dp[target];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

题目二：给定 m 个数字 0 和 n 个数字 1，以及一些由 0-1 构成的字符串，求利用这些数字最多可以构
成多少个给定的字符串，字符串只可以构成一次。

这是一个多维费用的 0-1 背包问题，有两个背包大小，0 的数量和 1 的数量。我们在这里直接展示三维空间压缩到二维后的写法。

//主函数
int findMaxForm(vector<string>&strs,int m,int n)
{
    vector<vector<int>> dp(m+1,vector<int>(n+1,0));
    for(const string & str:strs)
    {
        auto[count0,count1]=count(str);
        for(int i=m;i>=count1;--j)
        {
            for(int j=n;j>=count1;--j)
            {
                dp[i][j]=max(dp[i][j],1+dp[i-count0][j-count1]);
            }
        }
    }
    return dp[m][n];
}
//辅函数
pair<int,int>count(const string & s)
{
    int count0=s.length(),count1=0;
    for(const chat & c:s)
    {
        if(c=='1')
        {
            ++count1;
            --count0;
        }
    }
    return make_pair(count0,count1);
} 
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

题目三：给定一些硬币的面额，求最少可以用多少颗硬币组成给定的金额。

因为每个硬币可以用无限多次，这道题本质上是完全背包。我们直接展示二维空间压缩为一
维的写法。
这里注意，我们把 dp 数组初始化为 amount + 2 而不是-1 的原因是，在动态规划过程中有求最小值的操作，如果初始化成-1 则会导致结果始终为-1。至于为什么取这个值，是因为 i 最大可以取 amount + 1，而最多的组成方式是只用 1 元硬币，因此 amount + 2 一定大于所有可能的组合方式，取最小值时一定不会是它。在动态规划完成后，若结果仍然是此值，则说明不存在满足条件的组合方法，返回-1。

int coinChange(vector<int>&coins,int amount)
{
    if(coins.empty()) return -1;
    vector<int>dp(amount+1，amount+2);
    dp[0]=0;
    for(int i=1;i<=amount;++i)
    {
        for(const int & coin:coins)
        {
            if(i>=coin){
                dp[i]=min(dp[i],dp[i-coin]+1);
            }
        }
    }
    return dp[amount]==amount+2 ? -1:dp[amount];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

4.字符串编辑

题目一：给定两个字符串，已知你可以删除、替换和插入任意字符串的任意字符，求最少编辑几步可
以将两个字符串变成相同。

我们使用一个二维数组 dp[i][j]，表示将第一个字符串到位置 i 为止，和第二个字符串到位置 j 为止，最多需要几步编辑。当第 i 位和第 j 位对应的字符相同时，dp[i][j] 等 于 dp[i-1][j-1]；当二者对应的字符不同时，修改的消耗是 dp[i-1][j-1]+1，插入 i 位置/删除 j 位置的消耗是 dp[i][j-1] + 1，插入 j 位置/删除 i 位置的消耗是 dp[i-1][j] + 1。

int minDistance(string word1,string word2)
{
    int m=word1.length(),n=word.length();
    vector<vector<int>> dp(m+1，vector<int>(n+1,0));
    for(int i=0;i<=m;++i)
    {
        for(int j=0;j<=n;++j)
        {
            if(i==0){
                dp[i][j]=j;
            }
            else if(j==0){
                dp[i][j]=i;
            }
            else{
                dp[i][j]=min(
                    dp[i-1][j-1]+((word1[i-1]==word2[j-1])?0:1),
                    min(dp[i-1][j]+1,dp[i][j-1]+1));
            }
        }
    }
    return dp[m][n];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

题目二：给定一个字母 A，已知你可以每次选择复制全部字符，或者粘贴之前复制的字符，求最少需
要几次操作可以把字符串延展到指定长度。

不同于以往通过加减实现的动态规划，这里需要乘除法来计算位置，因为粘贴操作是倍数增加的。我们使用一个一维数组 dp，其中位置 i 表示延展到长度 i 的最少操作次数。对于每个位置j，如果 j 可以被 i 整除，那么长度 i 就可以由长度 j 操作得到，其操作次数等价于把一个长度为 1 的 A 延展到长度为 i/j。因此我们可以得到递推公式 dp[i] = dp[j] + dp[i/j]。

int minSteps(int n)
{
    vector<int>dp(n+1);
    int h=sqrt(n);
    for(int i=2;i<=n;++i)
    {
        dp[i]=i;
        for(int j=2;j<=h;++j)
        {
            if(i%j==0){
                dp[i]=dp[[j]+dp[i/j];
                break;
            }
        }
    }
    return dp[n];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

题目三：给定一个字符串和一个正则表达式（regular expression, regex），求该字符串是否可以被匹配。

我们可以使用一个二维数组 dp，其中 dp[i][j] 表示以 i 截止的字符串是否可以被以 j 截止的正则表达式匹配。根据正则表达式的不同情况，即字符、星号，点号，我们可以分情况讨论来更新 dp 数组，其具体代码如下。

bool isMatch(string s,string p)
{
    int m=s.size(),n=p.size();
    vector<vector<bool>> dp(m+1,vector<bool>(n+1,false));
    dp[0][0]=true;
    for(int i=1;i<n+1;++i)
    {
        if(p[i-1]=='*'){
            dp[0][i]=dp[0][i-2];
        }
    }
    for(int i=1;i<m+1;++i)
    {
        for(int j=1;k<n+1;++j)
        {
            if(p[j-1]=='.'){
                dp[i][j]=dp[i-1][j-1];
            }
            else if(p[j-1]!='*'){
                dp[i][j]=dp[i-1][j-1]&&p[j-1]==s[i-1];
            }
            else if(p[j-2]!=s[i-1]&&p[j-2]!='.'){
                dp[i][j]=dp[i][j-2];
            }
            else{
                dp[i][j]=dp[i][j-1]||dp[i-1][j]||dp[i][j-2];
            }
        }
    }
    return dp[m][n];
}
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