【动态规划七】背包问题

目录

0/1背包问题

一、【模板】01背包

二、分割等和子集

三、目标和

四、最后一块石头的重量 II

完全背包问题

一、【模板】完全背包

二、零钱兑换

三、零钱兑换 II

四、完全平方数

二维费用的背包问题

一、一和零

二、盈利计划

似包非包

组合总和

卡特兰数

不同的二叉搜索树

背包问题:

有1个背包，地上一堆物品，挑选一些物品放入背包中

问：能挑选物品的最大的价值是多少?

两个限制:

1.物品的属性(比如物品的体积，重量,  价值等)

2.背包的属性(背包的最大容量，承重等)

当物品的个数都限制为1个时，此时的背包问题就是0/1背包问题，因为每个物品选就是1个，不选就是0个

当物品的个数没有任何限制，都有无穷多个时，此时的背包问题就是完全背包问题

本篇博客介绍0/1背包问题

0/1背包问题

一、【模板】01背包

【模板】01背包_牛客题霸_牛客网 (nowcoder.com)icon-default.png?t=N7T8https://www.nowcoder.com/practice/fd55637d3f24484e96dad9e992d3f62e?tpId=230&tqId=2032484&ru=/exam/oj&qru=/ta/dynamic-programming/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D1961.题目解析

两个问题:

1.能装的物品的最大价值是多少?(可以装满，也可以不装满)

2.要求恰好装满，此时物品的最大价值是多少?

2.算法分析

问题一:

1.状态表示

背包问题本质还是线性dp问题，所以状态表示依旧是 经验 + 题目要求

dp[i]: 从前i个物品中挑选，所有选法中，能挑选的最大价值(×)

因为考虑第i个物品要不要放入背包的时候，必须先知道当前背包的容量才行

dp[i][j]: 从前i个物品中挑选，总体积不超过j, 所有选法中，能挑选出来的最大价值

2.状态转移方程

3.初始化

物品的编号从1开始，因此给dp表添加一行一列

第一行表示从前0个物品中挑选, 体积不超过j，能挑选的最大价值, 全是0

第一列表示从前i个物品中挑选, 体积不超过0，能挑选的最大价值, 全是0

4.填表顺序

从上往下填表

5.返回值

dp[n][V]

问题二:

1.状态表示

dp[i][j]: 从前i个物品中挑选，总体积正好等于 j,  所有选法中，能挑选出来的最大价值

2.状态转移方程

3.初始化

物品的编号从1开始，因此给dp表添加一行一列

dp[0][0] 表示从前0个物品中挑选，体积恰好为0的最大价值，什么都不选即可，那就是0

第一行的其余位置:

从前0个物品中挑选，价值恰好为j(j > 0)的最大价值，由于0个物品，所以凑不出价值恰好为j，因此值都是-1

第一列的其余位置:

从前i个物品中挑选，体积恰好为 0 的最大价值，一个物品都不选即可, 所以都是0

4.填表顺序

从上往下填表

5.返回值

dp[n][V] == -1 ? 0 : dp[n][V]

3.算法代码

#include <iostream>
using namespace std;
#include <string.h>

const int N = 1010;
int n, V, v[N], w[N]; //物品个数，背包体积，物品体积数组，物品价值数组
int dp[N][N];

int main() 
{
    //读入数据
    cin >> n >> V;
    for(int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];
    //第一问
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= V; j++)
        {
            dp[i][j] = dp[i-1][j];
            if(j >= v[i]) dp[i][j] = max(dp[i][j], dp[i-1][j-v[i]] + w[i]);
        }
    }
    cout << dp[n][V] << endl;
    //第二问
    memset(dp, 0, sizeof(dp)); //清空dp表
    for(int j = 1; j <= V; j++) //初始化dp表
        dp[0][j] = -1;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= V; j++)
        {
            dp[i][j] = dp[i-1][j];
            if(j >= v[i] &&  dp[i-1][j-v[i]] != -1) 
                dp[i][j] = max(dp[i][j], dp[i-1][j-v[i]] + w[i]);
        }
    }
    cout << (dp[n][V] == -1 ? 0 : dp[n][V])  << endl;
}

四、空间优化

我们在最开始讲解动态规划时就提到过，背包问题中经常可以使用空间优化，也就是不必使用二维数组，根据状态转移方程， 填写dp[i][j]时，只需要dp[i-1][j]与dp[i-1][j-v[i]]的值，因此只需要两行即可，也就是两个一维数组即可

而我们可以i进一步优化，也就是只需要一个一维数组即可, 也就是用dp[i-1][j-v[i]]的值与dp[i-1][j]的值在原始数组上更新dp[i][j]即可, 不过要注意，由于在原始数组上更新，防止发生覆盖，需要从右向左更新, 而代码只需要把所有的二位数组的第一维全删掉，填表的第二层for循环从右向左填并且可以把更新状态转移方程的条件放在循环条件的判断处即可

#include <iostream>
using namespace std;
#include <string.h>

const int N = 1010;
int n, V, v[N], w[N]; //物品个数，背包体积，物品体积数组，物品价值数组
int dp[N];

int main() 
{
    //读入数据
    cin >> n >> V;
    for(int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];
    //第一问
    for(int i = 1; i <= n; i++)
        for(int j = V; j >= v[i]; j--)
            dp[j] = max(dp[j], dp[j-v[i]] + w[i]);
    cout << dp[V] << endl;
    //第二问
    memset(dp, 0, sizeof(dp)); //清空dp表
    for(int j = 1; j <= V; j++) //初始化dp表
        dp[j] = -1;
    for(int i = 1; i <= n; i++)
        for(int j = V; j >= v[i]; j--)
            if(dp[j-v[i]] != -1) 
                dp[j] = max(dp[j], dp[j-v[i]] + w[i]);
    cout << (dp[V] == -1 ? 0 : dp[V])  << endl;
}

二、分割等和子集

416. 分割等和子集 - 力扣（LeetCode）icon-default.png?t=N7T8https://leetcode.cn/problems/partition-equal-subset-sum/1.题目解析

给定一个只包含正整数的数组，问是否可以将数组划分成元素和相等的两部分

2.算法分析

转化一下: 本质就是从数组中挑选一些数，看这些数之和能否等于sum/2即可

本题虽然不完全是0/1背包问题，但是可以划分到该0/1背包问题，因为每个数要么选，要么不选，相当于每个物品选或不选，而且本题比0/1背包问题更加简单，因为本题就是看数字能否凑成sum/2即可, 0/1背包问题求的是物品的价值和最大~

1.状态表示

dp[i][j]: 表示从前i个数中挑选，和能否凑成j

2.状态转移方程

3.初始化

添加有一行一列

dp[0][0] = true, 表示一个数都不选，是否可以凑成0， 当然可以

第一行的其余位置:  i =0, 表示一个数都不选，能否凑成1, 2, 3...., 当然不可以，值为false

第一列的其余位置:  j = 0, 表示从前i个数选，和能否凑成0, 一个都不选即可，值为true

4.填表顺序

从上往下填表

5.返回值

dp[n][sum/2]

3.算法代码

二维dp表:

class Solution {
public:
    bool canPartition(vector<int>& nums) 
    {
        //求数组所有元素的和
        int sum = 0;
        for(auto x : nums)
            sum += x;
        if(sum % 2) return false; //和是奇数, 直接返回false
        //1.创建dp表
        int m = nums.size(), aim = sum / 2;
        vector<vector<bool>> dp(m+1, vector<bool>(aim+1));
        //2.初始化
        for(int i = 0; i <= m ;i++)
            dp[i][0] = true;
        //3.填表
        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j <= aim; j++)
            {
                dp[i][j] = dp[i-1][j];
                if(j >= nums[i-1]) //注意下标的映射关系
                    dp[i][j] = dp[i][j] || dp[i-1][j-nums[i-1]];
            }
        }
        //4.返回值
        return dp[m][aim];
    }
};

滚动数组优化:

class Solution {
public:
    bool canPartition(vector<int>& nums) 
    {
        //求数组所有元素的和
        int sum = 0;
        for(auto x : nums)
            sum += x;
        if(sum % 2) return false; //和是奇数, 直接返回false
        //1.创建dp表
        int m = nums.size(), aim = sum / 2;
        vector<bool> dp(aim+1);
        //2.初始化
        dp[0] = true;
        //3.填表
        for(int i = 1; i <= m; i++)
            for(int j = aim; j >= nums[i-1]; j--)
                dp[j] = dp[j] || dp[j-nums[i-1]];
        //4.返回值
        return dp[aim];
    }
};

三、目标和

494. 目标和 - 力扣（LeetCode）icon-default.png?t=N7T8https://leetcode.cn/problems/target-sum/1.题目解析

给定一个非负nums数组和整数target, 给每个数组元素前可以加正负号，使得最终表达式运算的结果 == target即可，求满足条件的表达式的数目

2.算法分析

题目本质就是将数组划分成一堆正数和负数，假如正数的和是a, 负数的和的绝对值是b, 那么a-b==target, 而我们知道a + b == sum, 消元得 a = (target + sum) / 2;

因此问题就转化成了在数组中挑一些数，使得这些数的和等于a, 问共有多少种选法?? 此时与题目二基本一样了， 仍然属于0/1背包问题

1.状态表示

dp[i][j]: 从前i个数中挑选，总和正好等于j, 一共有多少种选法

2.状态转移方程

3.初始化

添加一行一列

dp[0][0] = 1, 表示 从前 0个数中挑选，总和恰好为0, 只要一个数都不选即可

第一行的其余位置: 表示 从前 0个数中挑选，总和恰好为j(>0), 显然不可能，因此值都为0

第一列的其余位置: 表示 从前 i个数中挑选，总和恰好为0, 但是nums中的元素值可能为0，因此可能有很多选法，但实际上不用初始化，因为初始化是为了防止越界，而第一列j = 0, 如果要用dp[i-1][j-nums[i]]这个状态转移方程，必须满足j >= nums[i], 也就是nums[i]只能等于0，此时dp[i-1][j-nums[i]]就是 dp[i-1][0]了，也就是正上方的值，因此不会越界, 因此无需初始化

4.填表顺序

从上往下填表

5.返回值

dp[n][a]

3.算法代码

二维dp表:

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) 
    {
        int sum = 0;
        for(auto x : nums)
            sum += x;
        int a = (sum + target) / 2;
        if(a < 0 || (sum + target) % 2) return 0; //a小于0或者sum+target是奇数, 直接返回0
 
        //1.创建dp表
        int n = nums.size();
        vector<vector<int>> dp(n+1, vector<int>(a+1));
        //2.初始化
        dp[0][0] = 1;
        //3.填表
        for(int i = 1; i <= n; i++)
        {
            for(int j = 0; j <= a; j++)
            {
                dp[i][j] = dp[i-1][j];
                if(j >= nums[i-1])
                    dp[i][j] += dp[i-1][j-nums[i-1]];
            }
        }
        //4.返回值
        return dp[n][a];
    }
};

滚动数组优化:

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) 
    {
        int sum = 0;
        for(auto x : nums)
            sum += x;
        int a = (sum + target) / 2;
        if(a < 0 || (sum + target) % 2) return 0; //a小于0或者sum+target是奇数, 直接返回0
 
        //1.创建dp表
        int n = nums.size();
        vector<int> dp(a+1);
        //2.初始化
        dp[0] = 1;
        //3.填表
        for(int i = 1; i <= n; i++)
            for(int j = a; j >= nums[i-1]; j--)
                dp[j] += dp[j-nums[i-1]];
        //4.返回值
        return dp[a];
    }
};

四、最后一块石头的重量 II

1049. 最后一块石头的重量 II - 力扣（LeetCode）icon-default.png?t=N7T8https://leetcode.cn/problems/last-stone-weight-ii/description/1.题目解析

之前我们已经在<<优先级队列>>博客中讲解了"最后一块石头的重量 I", 每次选两块最重的石头，而本题每次随机选两个石头进行碰撞，如果最后还剩余了一块石头，那么求最终剩余石头的最小重量，如果没有剩余石头，那么返回0

2.算法分析

本题的难点仍然在于如何把原问题进行转化，假设给定的数组元素是[a, b, c, d, e]

每次随机选两个石头进行碰撞, 可以发现最终结果无非是给原始数组元素添加上正负号，使得最终

的结果最小即可, 而我们可以把数分成两堆，一堆是正数，一堆是负数，假设正数的和是a, 负数和的绝对值是b, 已知a + b == sum, 求a - b 的最小值(也可能是b-a), 而a - b要最小，也就是a/b要最接近 sum的一半，此时问题就变成了0/1背包问题

把每一个数看成一个物品，每个物品的体积和价值都是nums[i], 挑选一些物品，背包的容量为sum / 2, 问能够装的的最大价值

1.状态表示

dp[i][j]: 从前i个数选，总和不超过j, 此时的最大和

2.状态转移方程

3.初始化

添加一行一列

第一行表示从前0个物品中挑选, 体积不超过j，能挑选的最大价值, 全是0

第一列表示从前i个物品中挑选, 体积不超过0，能挑选的最大价值, 全是0

4.填表顺序

从上往下

5.返回值

dp[n][m]相当于 a, sum - dp[n][m]是b, 由于dp[n][m] <= sum / 2的， b - a 一定 >= 0,  因此返回 b - a 即 sum - 2 * dp[n][m]

3.算法代码
二维dp表:

class Solution {
public:
    int lastStoneWeightII(vector<int>& nums) 
    {
        int n = nums.size();
        int sum = 0;
        for(auto x : nums)
            sum += x;
        int aim = sum / 2;
        //1.创建dp表
        vector<vector<int>> dp(n+1, vector<int>(aim+1));
        //2.填表
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= aim; j++)
            {
                dp[i][j] = dp[i-1][j];
                if(j >= nums[i-1])
                    dp[i][j] = max(dp[i][j], dp[i-1][j-nums[i-1]] + nums[i-1]);
            }
        }
        //3.返回值
        return sum - 2 * dp[n][aim];
    }
};

滚动数组优化:

class Solution {
public:
    int lastStoneWeightII(vector<int>& nums) 
    {
        int n = nums.size();
        int sum = 0;
        for(auto x : nums)
            sum += x;
        int aim = sum / 2;
        //1.创建dp表
        vector<int> dp(aim+1);
        //2.填表
        for(int i = 1; i <= n; i++)
            for(int j = aim; j >= nums[i-1]; j--)
                dp[j] = max(dp[j], dp[j-nums[i-1]] + nums[i-1]);
        //3.返回值
        return sum - 2 * dp[aim];
    }
};

完全背包问题

一、【模板】完全背包

完全背包和0/1背包的区别就是完全背包问题中每个物品的个数是不限的

【模板】完全背包_牛客题霸_牛客网 (nowcoder.com)icon-default.png?t=N7T8https://www.nowcoder.com/practice/237ae40ea1e84d8980c1d5666d1c53bc?tpId=230&tqId=2032575&ru=/exam/oj&qru=/ta/dynamic-programming/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D1961.题目解析

两个问题:

1.能装的物品的最大价值是多少?(可以装满，也可以不装满)

2.要求恰好装满，此时物品的最大价值是多少?

2.算法分析

问题一:

1.状态表示

dp[i][j]: 从前i个物品中挑选，总体积不超过j, 所有选法中，能挑选出来的最大价值

2.状态转移方程

3.初始化

添加一行一列

第一列不可能越界，因为第一列 j = 0, 而 dp[i][j-v[i]] + w[i] 是在 j >= v[i]的情况下成立的，因此v[i] 只能等于0, 因此不会越界。

第一行表示从前0个物品挑选，体积不超过 j的最大价值，全都初始化成0即可

4.填表顺序

从上往下填表，每一行从左往右

5.返回值

dp[n][V]

问题二:

1.状态表示

dp[i][j]: 从前i个物品中挑选，总体积正好等于j , 所有选法中，能挑选出来的最大价值

2.状态转移方程

3.初始化

添加一行一列

同理，第一列不可能越界

dp[0][0] 表示从前0个物品中挑选，体积恰好为0的最大价值，那就是0

第一行的其余位置: 从前0个物品中挑选，体积恰好为j(j>0)的最大价值，由于没有物品，所以体积不可能 > 0, 因此都是-1

4.填表顺序

从上往下填表，每一行从左往右

5.返回值

dp[n][V] == -1 ? 0 : dp[n][V]

3.算法代码

#include <iostream>
using namespace std;
#include <string.h>

const int N = 1001;
int n, V, v[N], w[N];
int dp[N][N];

int main() 
{
    cin >> n >> V;
    for(int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];
    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j <= V; j++)
        {
            dp[i][j] = dp[i-1][j];
            if(j >= v[i]) 
                dp[i][j] = max(dp[i][j], dp[i][j-v[i]] + w[i]);
        }
    }
    cout << dp[n][V] << endl;

    memset(dp, 0, sizeof(dp));
    for(int j = 1; j <= V; j++)
        dp[0][j] = -1;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= V; j++)
        {
            dp[i][j] = dp[i-1][j];
            if(j >= v[i] && dp[i][j-v[i]] != -1)
                dp[i][j] = max(dp[i][j], dp[i][j-v[i]] + w[i]);
        }
    }
    cout << (dp[n][V] == -1 ? 0 : dp[n][V]) << endl;
}

4.空间优化

更新dp[i][j]会用到两个绿色格子的值，而空间优化的本质就是只用一个一维dp表

黄色表示还没更新的值，绿色表示已经更新过的值，因此要填dp[i][j], 必须要保证用到的两个格子已经变成了绿色格子才可以，因此必须从左往右填一维dp表!!  这也是和0/1背包空间优化不同的地方，0/1背包是从右往左填一维dp表的

#include <iostream>
using namespace std;
#include <string.h>

const int N = 1001;
int n, V, v[N], w[N];
int dp[N];

int main() 
{
    //输入
    cin >> n >> V;
    for(int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];
    //问题一
    for(int i = 1; i <= n; i++)
        for(int j = v[i]; j <= V; j++)
            dp[j] = max(dp[j], dp[j-v[i]] + w[i]);
    cout << dp[V] << endl;
    //问题二
    memset(dp, 0, sizeof(dp));
    for(int j = 1; j <= V; j++)
        dp[j] = -1;
    for(int i = 1; i <= n; i++)
        for(int j = v[i]; j <= V; j++)
            if(dp[j-v[i]] != -1)
                dp[j] = max(dp[j], dp[j-v[i]] + w[i]);
    cout << (dp[V] == -1 ? 0 : dp[V]) << endl;
}

补充:

在问题二的代码中，用状态转移方程之前要先判断要用到的状态是否存在，事实上，我们也可以不用判断，只要保证求完max之后不会对结果产生影响即可，因此在初始化的时候，可以初始化成-0x3f3f3f3f即可

#include <iostream>
using namespace std;
#include <string.h>

const int N = 1001;
int n, V, v[N], w[N];
int dp[N];

int main() 
{
    //输入
    cin >> n >> V;
    for(int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];
    //问题一
    for(int i = 1; i <= n; i++)
        for(int j = v[i]; j <= V; j++)
            dp[j] = max(dp[j], dp[j-v[i]] + w[i]);
    cout << dp[V] << endl;
    //问题二
    memset(dp, 0, sizeof(dp));
    for(int j = 1; j <= V; j++)
        dp[j] = -0x3f3f3f3f;
    for(int i = 1; i <= n; i++)
        for(int j = v[i]; j <= V; j++)
            dp[j] = max(dp[j], dp[j-v[i]] + w[i]);
    cout << (dp[V] < 0 ? 0 : dp[V]) << endl;
}

二、零钱兑换

322. 零钱兑换 - 力扣（LeetCode）icon-default.png?t=N7T8https://leetcode.cn/problems/coin-change/1.题目解析

给定整数数组coins和一个整数amount表示总金额，求凑成amount所需要的硬币最小个数

2.算法分析

1.状态表示

dp[i][j]: 从前 i 个硬币中挑选，总和正好等于 j, 所有选法中，最少的硬币个数

2.状态转移方程

3.初始化

dp[0][0] = 0

第一行其余位置: 0x3f3f3f3f (参考上一道题目的补充内容)

4.填表顺序

从上往下填表, 每一行从左往右

5.返回值

dp[n][amout] >= 0x3f3f3f3f ? -1 : dp[n][amount]

3.算法代码

二维dp表

class Solution {
public:
    int coinChange(vector<int>& coins, int amount)
    {
        int n = coins.size();
        const int INF = 0x3f3f3f3f;
        vector<vector<int>> dp(n+1, vector<int>(amount+1));
        for(int j = 1; j <= amount; j++)
            dp[0][j] = INF;
        for(int i = 1; i <= n; i++)
        {
            for(int j = 0; j <= amount; j++)
            {
                dp[i][j] = dp[i-1][j];
                if(j >= coins[i-1])
                    dp[i][j] = min(dp[i][j], dp[i][j-coins[i-1]] + 1);
            }
        }
        return dp[n][amount] >= INF ? -1 : dp[n][amount]; 
    }
};

空间优化:

class Solution {
public:
    int coinChange(vector<int>& coins, int amount)
    {
        int n = coins.size();
        const int INF = 0x3f3f3f3f;
        vector<int> dp(amount+1, INF);
        dp[0] = 0;
        for(int i = 1; i <= n; i++)
            for(int j = coins[i-1]; j <= amount; j++)
                dp[j] = min(dp[j], dp[j-coins[i-1]] + 1);
        return dp[amount] >= INF ? -1 : dp[amount]; 
    }
};

三、零钱兑换 II

518. 零钱兑换 II - 力扣（LeetCode）icon-default.png?t=N7T8https://leetcode.cn/problems/coin-change-ii/description/1.题目解析

本题求的是凑成 amount 的硬币的组合个数

2.算法分析

1.状态表示

dp[i][j]: 从前 i 个硬币中挑选，总和正好等于 j, 一共有多少种选法

2.状态转移方程

3.初始化

dp[0][0] = 1, 表示从前 0 个硬币中挑选，总和恰好为0的，共有1种选法(就是什么都不选)

第一行的其余位置初始化成0即可, 表示从前 0 个硬币中挑选，总和恰好为 j (>0)，共有0种选法

4.填表顺序

从上往下填表，每一行从左往右

5.返回值

dp[n][amount]

3.算法代码

二维dp表

class Solution
{
public:
    int change(int amount, vector<int>& coins) 
    {
        int n = coins.size();
        vector<vector<int>> dp(n+1, vector<int>(amount+1));
        dp[0][0] = 1;
        for(int i = 1; i <= n; i++)
        {
            for(int j = 0; j <= amount; j++)
            {
                dp[i][j] = dp[i-1][j];
                if(j >= coins[i-1])
                    dp[i][j] += dp[i][j-coins[i-1]];
            }
        }
        return dp[n][amount];
    }
};

空间优化 

class Solution
{
public:
    int change(int amount, vector<int>& coins) 
    {
        int n = coins.size();
        vector<int> dp(amount+1);
        dp[0] = 1;
        for(int i = 1; i <= n; i++)
            for(int j = coins[i-1]; j <= amount; j++)
                dp[j] += dp[j-coins[i-1]];
        return dp[amount];
    }
};

四、完全平方数

279. 完全平方数 - 力扣（LeetCode）icon-default.png?t=N7T8https://leetcode.cn/problems/perfect-squares/1.题目解析

给定一个数n,  返回和为n的完全平方数的最小数量

2.算法分析

转化成完全背包问题

1.状态表示

dp[i][j]: 从前 i 个完全平方数中挑选，总和正好等于 j, 所有选法中，最小的数量

2.状态转移方程

3.初始化

dp[0][0] = 0, 从前 0 个完全平方数中挑选，总和恰好等于 0，只需要0个完全平方数即可

第一行其余位置:

从前 0 个完全平方数中挑选，总和恰好等于 j( > 0)，显然做不到，初始化成为0x3f3f3f3f即可

4.填表顺序

从上往下填表，每一行从左往右

5.返回值

dp[根号下n][n]

3.算法代码

二维dp表

class Solution 
{
public:
    int numSquares(int n) 
    {
        //1.创建dp表
        int m = sqrt(n);
        vector<vector<int>> dp(m+1, vector<int>(n+1));
        const int INF = 0x3f3f3f3f;
        //2.初始化
        for(int j = 1; j <= n; j++)
            dp[0][j] = INF;
        //3.填表
        for(int i = 1; i <= m; i++)
        {
            for(int j = 0; j <= n; j++)
            {
                dp[i][j] = dp[i-1][j];
                if(j >= i*i)  
                    dp[i][j] = min(dp[i][j], dp[i][j-i*i] + 1);
            }
        } 
        //4.返回值
        return dp[m][n];
    }
};

 空间优化 

class Solution 
{
public:
    int numSquares(int n) 
    {
        //1.创建dp表
        int m = sqrt(n);
        vector<int> dp(n+1);
        const int INF = 0x3f3f3f3f;
        //2.初始化
        for(int j = 1; j <= n; j++)
            dp[j] = INF;
        //3.填表
        for(int i = 1; i <= m; i++)
            for(int j = i*i; j <= n; j++)
                dp[j] = min(dp[j], dp[j-i*i] + 1);
        //4.返回值
        return dp[n];
    }
};

二维费用的背包问题

一、一和零

474. 一和零 - 力扣（LeetCode）icon-default.png?t=N7T8https://leetcode.cn/problems/ones-and-zeroes/description/1.题目解析

给你一个二进制字符串数组 strs 和两个整数 m 和 n ，找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1

2.算法分析

本质就是在字符串数组中挑选一些字符串出来，需要满足两个条件(1和0的个数限制)， 这类问题就是二维费用的背包问题(也分为二维费用的0/1背包问题 和 二维费用的完全背包问题

1.状态表示
dp[i][j][k] 表示 从前 i 个字符串中挑选，字符0的个数不超过j, 字符1的个数不超过k, 所有的选法中，最大的长度

2.状态转移方程

3.初始化

当i=0, 表示从前 0 个字符串中挑选，字符0的个数不超过j, 字符1的个数不超过k, 没有字符串可选，因此长度就是0, 全部初始化成0即可

4.填表顺序

i从小到大即可

5.返回值

dp[len][m][n]

len表示字符串的长度

3.算法代码

三维dp表

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) 
    {
        int len = strs.size();
        vector<vector<vector<int>>> dp(len + 1, vector<vector<int>>(m+1, vector<int>(n+1)));
        for(int i = 1; i <= len; i++)
        {
            //统计当前字符串中0/1字符的个数
            int a = 0, b = 0;
            for(auto ch : strs[i-1])
                if(ch == '0') a++;
                else b++;
            for(int j = 0; j <= m; j++)
            {
                for(int k = 0; k <= n; k++)
                {
                    dp[i][j][k] = dp[i-1][j][k];
                    if(j >= a && k >= b)
                        dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-a][k-b] + 1); 
                }
            }
        }
        return dp[len][m][n];
    }
};

空间优化

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) 
    {
        int len = strs.size();
        vector<vector<int>> dp(m+1, vector<int>(n+1));
        for(int i = 1; i <= len; i++)
        {
            //统计当前字符串中0/1字符的个数
            int a = 0, b = 0;
            for(auto ch : strs[i-1])
                if(ch == '0') a++;
                else b++;
            for(int j = m; j >= a; j--)
                for(int k = n; k >= b; k--)
                        dp[j][k] = max(dp[j][k], dp[j-a][k-b] + 1); 
        }
        return dp[m][n];
    }
};

二、盈利计划

879. 盈利计划 - 力扣（LeetCode）icon-default.png?t=N7T8https://leetcode.cn/problems/profitable-schemes/1.题目解析

n表示员工人数, minProfit表示至少需要产生的利润，profit数组和group数组对应, 第i种工作需要group[i]个员工完成，会产生profit[i]的利润，现在问有多少种选择工作的方法，使得能够产生的利润>=minProfit

2.算法分析

本质是二维费用的0/1背包问题

1.状态表示

dp[i][j][k]: 从前i个工作中挑选，总人数不超过 j, 总利润至少为 k, 一共有多少种选法

2.状态转移方程

3.初始化

dp[0][j][0],  i = 0表示没有计划, 没有计划就没有利润，因此 k 也是0，此时什么都不选就满足条件，因此将dp[0][j][0]初始化成1

4.填表顺序

i从小到大即可

5.返回值

dp[len][n][m]

len是group数组或profit数组的长度

3.算法代码

三维dp表

class Solution {
public:
    int profitableSchemes(int n, int m, vector<int>& g, vector<int>& p) 
    {
        const int MOD = 1e9 + 7;
        //1.创建dp表
        int len = g.size();
        vector<vector<vector<int>>> dp(len+1, vector<vector<int>>(n+1, vector<int>(m+1)));
        //2.初始化dp表
        for(int j = 0; j <= n; j++)
            dp[0][j][0] = 1;
        //3.填表
        for(int i = 1; i <= len; i++)
        {
            for(int j = 0; j <= n; j++)
            {
                for(int k = 0; k <= m; k++)
                {
                    dp[i][j][k] += dp[i-1][j][k];
                    if(j >= g[i-1])
                        dp[i][j][k] += dp[i-1][j-g[i-1]][max(0, k-p[i-1])];
                    dp[i][j][k] %= MOD;
                }
            }
        }
        //4.返回值
        return dp[len][n][m];
    }
};

空间优化

class Solution {
public:
    int profitableSchemes(int n, int m, vector<int>& g, vector<int>& p) 
    {
        const int MOD = 1e9 + 7;
        //1.创建dp表
        int len = g.size();
        vector<vector<int>> dp(n+1, vector<int>(m+1));
        //2.初始化dp表
        for(int j = 0; j <= n; j++)
            dp[j][0] = 1;
        //3.填表
        for(int i = 1; i <= len; i++)
            for(int j = n; j >= g[i-1]; j--)
                for(int k = m; k >= 0; k--)
                {
                    dp[j][k] += dp[j-g[i-1]][max(0, k-p[i-1])];   
                    dp[j][k] %= MOD;
                }
        //4.返回值
        return dp[n][m];
    }
};

似包非包

组合总和

377. 组合总和 Ⅳ - 力扣（LeetCode）icon-default.png?t=N7T8https://leetcode.cn/problems/combination-sum-iv/description/1.题目解析

给定一个nums数组和target目标值，从nums数组中找出和为target的排列个数，每个数可以选择无数次，注意顺序不同算是不同的情况

2.算法分析

"背包问题"研究的本质是限制条件下的组合问题，也就是我们挑选物品没有考虑顺序，而本题是要考虑顺序的，因此本题不能用"完全背包"的方法来解决

1.状态表示

本题的状态表示方式是之前的博客没有提到的:

根据分析问题的过程中，发现重复子问题，抽象出一个状态表示

[a, b, c, d, e], 在整个区间中选择凑成总和为target, 如果第一个数选了a, 那只需要在整个区间凑成总和为target-a即可, 于是我们发现了重复子问题

dp[i]表示: 凑成总和为 i, 一共有多少种排列数

2.状态转移方程

3.初始化

dp[0] = 1，因为数组中元素>=1，因此要凑出总和为0, 什么都不选，也就是空集

4.填表顺序

从左往右

5.返回值

dp[target]

3.算法代码

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) 
    {
        vector<double> dp(target+1);
        dp[0] = 1;
        for(int i = 1; i <= target; i++)
            for(auto x : nums)
                if(i >= x) dp[i] += dp[i-x];
        return dp[target];
    }
};

卡特兰数

不同的二叉搜索树

96. 不同的二叉搜索树 - 力扣（LeetCode）icon-default.png?t=N7T8https://leetcode.cn/problems/unique-binary-search-trees/description/1.题目解析

给定整数n, 求由n个节点(值是1到n)组成的二叉搜索树有多少种

2.算法分析

1.状态表示 --- 根据分析问题的过程中，发现重复子问题，抽象出一个状态表示

随便选一个数，作为根，此时就只需要分析左子树和右子树有多少种二叉搜索树, 然后乘起来

dp[i]表示: 节点个数为i时，一共有多少种二叉搜索树

2.状态转移方程

节点为[1, 2, ... i], 随便选一个数j作为根，则左子树的节点个数为j-1, 右子树的节点个数为i-j,

dp[i] += dp[j-1] * dp[i-j]

(1<= j <= i)

3.初始化

dp[0] = 1，空树也是一颗二叉搜索树

4.填表顺序

从左往右

5.返回值

dp[n]

3.算法代码

class Solution {
public:
    int numTrees(int n) 
    {
        vector<int> dp(n+1);
        dp[0] = 1;
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= i; j++)
                dp[i] += dp[j-1] * dp[i-j];
        return dp[n];
    }
};

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/636722.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

“Excel+中文编程”衍生新型软件，WPS用户：自家孩子

“Excel+中文编程”衍生新型软件，WPS用户：自家孩子

你知道吗&#xff0c;我们中国人有时候真的挺有创新精神的。 你可能熟悉Excel表格&#xff0c;也可能听说过中文编程&#xff0c;但你有没有脑洞大开&#xff0c;想过如果把这两者结合起来&#xff0c;会碰撞出什么样的火花呢&#xff1f; 别不信&#xff0c;跟着我来看看吧&a…
阅读更多...
惠普电脑怎么进入bios？图文教程助你轻松上手！

惠普电脑怎么进入bios？图文教程助你轻松上手！

进入BIOS&#xff08;基本输入/输出系统&#xff09;是在电脑启动时进行硬件初始化和设置的重要步骤之一。对于惠普&#xff08;HP&#xff09;电脑用户来说&#xff0c;了解如何进入BIOS是解决一些硬件和系统问题的关键。本文将介绍惠普电脑怎么进入bios的三种方法&#xff0c…
阅读更多...
Wireshark抓取PROFINET包问题总结

Wireshark抓取PROFINET包问题总结

1.如何导入GSD文件 ? 打开Wireshark在【编辑】->【首选项】->【Protocols】->【PNIO】&#xff0c;设置GSD文件的路径。 添加完成后&#xff0c;就可以解析报文了 2.Frame check sequence和FCS Status显示 unverified ? 【编辑】->【首选项】->【Protocols】…
阅读更多...
Kafka-集群管理者（Controller）选举机制、任期（epoch）机制

Kafka-集群管理者（Controller）选举机制、任期（epoch）机制

Kafka概述 Kafka-集群管理者&#xff08;Controller&#xff09;选举机制 Kafka中的Controller是Kafka集群中的一个特殊角色&#xff0c;负责对整个集群进行管理和协调。Controller的主要职责包括分区分配、副本管理、Leader选举等。当当前的Controller节点失效或需要进行重新…
阅读更多...
Redis常见数据类型(3)-String, Hash

Redis常见数据类型(3)-String, Hash

目录 String 命令小结 内部编码 典型的使用场景 缓存功能 计数功能 共享会话 手机验证码 Hash 哈希 命令 hset hget hexists hdel hkeys hvals hgetall hmget hlen hsetnx hincrby hincrbyfloat String 上一篇中介绍了了String里的基本命令, 接下来总结一…
阅读更多...
什么是谷歌留痕？

什么是谷歌留痕？

其实它就是指你的网站在谷歌中留下的种种痕迹&#xff0c;无论你是在做外链&#xff0c;还是优化网站内容&#xff0c;或是改善用户体验&#xff0c;所有这些都会在谷歌的搜索引擎里留下一些“脚印”&#xff0c;用比较seo一点的说法&#xff0c;指的是网站在其构建和优化过程中…
阅读更多...
5.22 R语言-正态性检验

5.22 R语言-正态性检验

正态性检验 正态性检验的目的是确定一组数据是否符合正态分布&#xff08;也称高斯分布&#xff09;。在统计分析和数据建模中&#xff0c;正态性假设是许多统计方法和模型的基础。了解数据是否符合正态分布有助于选择适当的统计方法和确保分析结果的有效性。 本文主要从概率…
阅读更多...
安全牛专访美创CTO周杰：数据安全进入体系化建设阶段，数据安全管理平台应用正当时

安全牛专访美创CTO周杰：数据安全进入体系化建设阶段，数据安全管理平台应用正当时

在数字经济时代&#xff0c;数据作为生产要素发挥越来越重要的作用&#xff0c;数据安全也得到了前所未有的重视。而随着数据安全能力已经进入了相对体系化建设的阶段&#xff0c;更加智能化、协同化的新一代数据安全管理平台得到了各类企业组织的广泛关注。 本期牛人访谈邀请到…
阅读更多...
java中写word换行符 poi 换行

java中写word换行符 poi 换行

省流&#xff1a; 表格外的文本&#xff0c;使用“\r”或者“(char)11”来换行&#xff0c;建议用"\r"。 表格内的文本&#xff0c;使用“(char)11”来换行。 正文&#xff1a; 测试用word文档&#xff1a; t1.doc内容如下&#xff1a; t2.doc内容如下&#xff…
阅读更多...
芯片半导体研发公司的数据防泄漏解决方案

芯片半导体研发公司的数据防泄漏解决方案

在当今信息化时代&#xff0c;半导体研发公司的数据防泄密工作显得尤为重要。半导体行业涉及大量的核心技术、研发文档和客户信息&#xff0c;一旦数据泄露&#xff0c;将给企业带来无法估量的损失。因此&#xff0c;建立一套有效的数据防泄密解决方案成为半导体研发公司的当务…
阅读更多...
最新腾讯音乐人挂机脚本，号称日赚300+【永久脚本+使用教程】

最新腾讯音乐人挂机脚本，号称日赚300+【永久脚本+使用教程】

项目介绍 首先需要认证腾讯音乐人&#xff0c;上传自己的歌曲&#xff0c;然后用小号通过脚本去刷自己的歌曲 &#xff0c;赚取播放量 &#xff0c;1万播放大概就是50到130之间 腾讯认证不需要露脸&#xff0c;不吞量&#xff0c;不封号 脚本&#xff0c;全自动无脑挂机&…
阅读更多...
链表经典OJ问题【环形链表】

链表经典OJ问题【环形链表】

题目导入 题目一&#xff1a;给你一个链表的头节点 head &#xff0c;判断链表中是否有环 题目二&#xff1a;给定一个链表的头节点 head &#xff0c;返回链表开始入环的第一个节点。 如果链表无环&#xff0c;则返回 NULL。 题目一 给你一个链表的头节点 head &#xff0c;…
阅读更多...
【CTF Web】CTFShow web3 Writeup（SQL注入+PHP+UNION注入）

【CTF Web】CTFShow web3 Writeup（SQL注入+PHP+UNION注入）

web3 1 管理员被狠狠的教育了&#xff0c;所以决定好好修复一番。这次没问题了。 解法 注意到&#xff1a; <!-- flag in id 1000 -->但是拦截很多种字符。 if(preg_match("/or|\-|\\|\*|\<|\>|\!|x|hex|\/i",$id)){die("id error"); }使用…
阅读更多...
Hadoop+Spark大数据技术 实验7 Spark综合编程

Hadoop+Spark大数据技术 实验7 Spark综合编程

删除字符串 package HelloPackageimport scala.io.StdInobject DeleteStr {def main(args: Array[String]): Unit {var str1 ""var str2 ""var i 0var j 0var flag 0print("请输入第一个字符串:")str1 StdIn.readLine()print("请输…
阅读更多...
Docker简单使用

Docker简单使用

1.简单认识 软件的打包技术&#xff0c;就是将打乱的多个文件打包为一个整体&#xff0c;比如想使用nginx&#xff0c;需要先有一台linux的虚拟机&#xff0c;然后在虚拟机上安装nginx.比如虚拟机大小1G&#xff0c;nginx100M。当有了docker后我们可以下载nginx 的镜像文件&am…
阅读更多...
Excel/WPS《超级处理器》同类项处理，合并同类项与拆分同类项目

Excel/WPS《超级处理器》同类项处理，合并同类项与拆分同类项目

在工作中处理表格数据&#xff0c;经常会遇到同类项处理的问题&#xff0c;合并同类项或者拆分同类项&#xff0c;接下来介绍使用超级处理器工具如何完成。 合并同类项 将同一列中的相同内容合并为一个单元格。 1&#xff09;用分隔符号隔开 将AB列表格&#xff0c;合并后为…
阅读更多...
chrome125.0.6422.60驱动包下载

chrome125.0.6422.60驱动包下载

百度网盘地址：https://pan.baidu.com/s/1DAr_O58GQ6m4sk_QePZscA?pwd=5t0j 提取码：5t0j Chrome驱动包（ChromeDriver）是一个用于支持自动化测试的工具，它提供了对Google Chrome浏览器的控制，使您可以编写和运行自动化脚本来测试网站。这个驱动程序是由Selenium项目开…
阅读更多...
Web安全：SQL注入之时间盲注原理+步骤+实战操作

Web安全：SQL注入之时间盲注原理+步骤+实战操作

「作者简介」&#xff1a;2022年北京冬奥会网络安全中国代表队&#xff0c;CSDN Top100&#xff0c;就职奇安信多年&#xff0c;以实战工作为基础对安全知识体系进行总结与归纳&#xff0c;著作适用于快速入门的 《网络安全自学教程》&#xff0c;内容涵盖系统安全、信息收集等…
阅读更多...
【Python】 Python脚本中的#!（Shebang）：使用指南与最佳实践

【Python】 Python脚本中的#!（Shebang）：使用指南与最佳实践

基本原理 在Python脚本编程中&#xff0c;#!&#xff08;通常称为shebang&#xff09;是一个特殊的行&#xff0c;它告诉操作系统使用哪个解释器来执行脚本。在Unix-like系统中&#xff0c;shebang是必需的&#xff0c;因为它允许脚本作为独立的程序运行&#xff0c;而不需要显…
阅读更多...
mysql 、oss 结合使用

mysql 、oss 结合使用

以下是一个使用 Express、MySQL、OSS 和 axios 的 Node.js 示例。这个示例创建了一个 Express 服务器&#xff0c;该服务器有一个路由用于处理视频上传的请求。视频文件首先被上传到 OSS&#xff0c;然后视频的 OSS URL 被存储到 MySQL 数据库。 首先&#xff0c;我们需要安装必…
阅读更多...
最新文章

Copyright @ 2022~2023