【动态规划】完全背包问题应用
完全背包问题应用
- 1.零钱兑换
- 2.零钱兑换 II
- 3.完全平方数
点赞👍👍收藏🌟🌟关注💖💖
你的支持是对我最大的鼓励，我们一起努力吧!😃😃
1.零钱兑换
题目链接： 322. 零钱兑换
题目分析：
有一堆硬币，从这些硬币中选一些硬币，看能凑成总金额amount所需的 最少的硬币个数。这是一个典型的背包问题。你可以认为每种硬币的数量是无限的，这句话很重要。看到这个无限你就要想到这是一个完全背包问题。
算法原理：
1.状态表示
dp[i][j] 表示：从前 i 个硬币中挑选，总和正好等于j，所有选法中，最少硬币个数。
2.状态转移方程
根据最后一个位置，划分情况
不选 i，说明所有选法中都不包含第 i 个硬币，相当于从去 1 ~ i - 1 这个区间去选，就是dp[i-1][j]
选1个i，这时就有 i 这个硬币了，然后仅需去 1 ~ i - 1 区间去选一个 不超过j - coins[i]的最少硬币个数，然后在加上 i 这个硬币个数
同理，选2个 i、选3个 i都是上面的分析思路
发现填一个状态的时候发现这个状态时候很多状态拼接而成的，这个时候我们要想到策略把这些状态用一个或者两个状态来表示。
在完全背包哪里我们已经分析过了，这里直接写，然后我们取所有情况的最小值。
3.初始化
- 多开一行一列
- 里面的值要保证后序的填表是正确的
- 下标的映射关系
第一列不用初始化，因为用到dp[i][j-coins[i]] 前提 j >= coins[i]，所以不会越界。我们只初始化第一行。
第一行表示硬币为空，当 j = 0表示总和为0，不选就行了
当 j = 1、2、3…，硬币为空，根本凑不出总和是这些的情况。之前完全背包说过这些都给-1然后特判一下，但是在优化的时候有说过这些无效的情况仅需不让它们参与我们求dp[i][j]就可以了，这里我们求得是min，因此我们可以给这些位置初始化为无穷大，这样即使情况不存在求min也不会影响。注意这里给无穷大不能给INT_MAX，首先 INT_MAX + 1 会越界Leetcode会报错，其次INT_MAX + 1 会是一个很小的数求min就会用到它。这里我们可以给0x3f3f3f3f，可以保证在这个算法中它是最大的，并且用来做加法也不会越界。
4.填表顺序
填dp[i][j]会用到上面和左边的值，因此从上往下填写每一行，每一行从左往右。
5.返回值
dp[i][j] 表示：从前 i 个硬币中挑选，总和正好等于j，所有选法中，最少硬币个数。我们要的是从整个数组中选，总和等于amount，最少硬币个数，因此返回dp[n][amount]，但是可能整个数组也凑不出总和等于amount，所以返回判断一下
dp[n][amount] >= INF ? : -1 : dp[n][amount]
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
// 1.创建 dp 表
// 2.初始化
// 3.填表
// 4.返回值
const int INF = 0x3f3f3f3f;
int n = coins.size();
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) {
// 1.创建 dp 表
// 2.初始化
// 3.填表
// 4.返回值
const int INF = 0x3f3f3f3f;
// int n = coins.size();
// 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];
//优化
int n = coins.size();
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];
}
};
2.零钱兑换 II
题目链接：518. 零钱兑换 II
题目分析：
当看到硬币有无限个，我们就该想到这是一道完全背包问题。
算法原理：
1.状态表示
dp[i][j] 表示：从前 i 个硬币中挑选，总和正好等于j，一共有多少种选法
2.状态转移方程
根据最后一个位置，划分情况
不选 i，说明所有选法中都不包含第 i 个硬币，相当于从去 1 ~ i - 1 这个区间去选，就是dp[i-1][j]
选1个i，这时就有 i 这个硬币了，然后仅需去 1 ~ i - 1 区间去选一个 总和正好等于j - coins[i]，注意问的是多少种选法， i 这个硬币仅需跟在所有选法后面就行了，不需要加1。
选2个i，选3个i … 都是类似分析
发现填一个状态的时候发现这个状态时候很多状态拼接而成的，这个时候我们要想到策略把这些状态用一个或者两个状态来表示。
在完全背包哪里我们已经分析过了，这里直接写。
注意这里直接写，是因为前面已经分析过了，这个状态只适用于完全背包。
最后我们将所有情况加起来，注意 j-coins[i] 不一定存在。必须要满足 j >= coins[i]，才能用这个状态。
3.初始化
- 多开一行一列
- 里面的值要保证后序的填表是正确的
- 下标的映射关系
第一列不用初始化，因为用到dp[i][j-coins[i]] 前提 j >= coins[i]，所以不会越界。我们只初始化第一行。
第一行表示硬币为空，当 j = 0表示总和为0，不选就行了，这是一种选法
当j = 1、2、3…，硬币为空根本凑不出总和等于j的选法。直接都给0就行了
4.填表顺序
填dp[i][j]会用到上面和左边的值，因此从上往下填写每一行，每一行从左往右。
5.返回值
dp[i][j] 表示：从前 i 个硬币中挑选，总和正好等于j，一共有多少种选法，我们要的是从整个数组种选总和等于amount一共有多少种选法，正好就是dp[n][amount]
class Solution {
public:
int change(int amount, vector<int>& coins) {
// 1.创建 dp 表
// 2.初始化
// 3.填表
// 4.返回值
// 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];
//优化
// 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];
// vector<int> dp(amount + 1);
// dp[0] = 1;
// for(int i = 0; i < coins.size(); ++i)//用不到i
// for(int j = coins[i]; j <= amount; ++j)
// dp[j] += dp[j - coins[i]];
// return dp[amount];
vector<int> dp(amount + 1);
dp[0] = 1;
for(auto x : coins)
for(int j = x; j <= amount; ++j)
dp[j] += dp[j - x];
return dp[amount];
}
};
3.完全平方数
题目链接： 279. 完全平方数
题目分析：
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数：比如说1^2 = 1，2^2 = 4，3^2 = 9。1、4、9就是完全平方数。
算法原理：
从左往右开始挑完全平方数，一个数可以挑多次，挑出来的数只要等于n即可。如果对背包问题比较敏感，这就是背包问题，并且是完全背包问题。
1.状态表示
dp[i][j] 表示：从前 i 个完全平方数种挑选，总和正好等于 j，所有选法中，最少的数量
2.状态转移方程
根据最后一个位置，划分情况
不选 i^2，说明所有选法中都不包含 i^2 这个平方数，相当于从去 1 ~ i - 1 这个区间去选，就是dp[i-1][j]
选1个 i^2，然后在去1 ~ i - 1区间挑一个总和等于 j - i^2的最少数量，然后在加上选的 i^2这一个数。
同理选2个 i^2，3个 i^2…， 和上面分析一样
发现填一个状态的时候发现这个状态时候很多状态拼接而成的，这个时候我们要想到策略把这些状态用一个或者两个状态来表示。
在完全背包哪里我们已经分析过了，这里直接写。
然后从所有情况找最小值
3.初始化
- 多开一行一列
- 里面的值要保证后序的填表是正确的
- 下标的映射关系
第一列不用初始化，因为用到dp[i][j-coins[i]] 前提 j >= coins[i]，所以不会越界。我们只初始化第一行。
第一行表示完全平方数为0，当 j = 0表示总和为0，不选就行了，最少数量为0
当 j = 1、2…，完全平方数为0，根本凑不出和为 j，然后我们填dp[i][j]要最小值，为了不让这些位置得值影响填表，因此可以给0x3f3f3f3f
4.填表顺序
填dp[i][j]会用到上面和左边的值，因此从上往下填写每一行，每一行从左往右。
5.返回值
dp[i][j] 表示：从前 i 个完全平方数中挑选，总和正好等于 j，所有选法中，最少的数量，但是我们要的是从整个完全平方数种选总和正好等于n最少数量。这里有一个问题 i 取到哪里比较好呢？
我们绝对不会选一个完全平方数会比n大，所以说下标的平方应该小于等于n
所以我们最终返回的是 dp[√n][n]，同时建表的时候也应该是（√n + 1）*（n + 1）规模的。
class Solution {
public:
int numSquares(int n) {
// int m = sqrt(n);
// vector<vector<int>> dp(m + 1, vector<int>(n + 1));
// for(int j = 1; j <= n; ++j) dp[0][j] = 0x3f3f3f3f;
// 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);
// }
// return dp[m][n];
//优化
int m = sqrt(n);
vector<int> dp(n + 1,0x3f3f3f3f);
dp[0] = 0;
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);
return dp[n];
}
};