当前位置:   article > 正文

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

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
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/691620
推荐阅读
相关标签
  

闽ICP备14008679号