学校网站开发图片素材,定制网站建设需要多少钱,网站推广应该怎么做?,网站建设需求材料文章目录 一、题目二、题解方法一#xff1a;完全背包问题的变体#xff08;版本1#xff09;方法二#xff1a;完全背包问题变体#xff08;版本2#xff09; 三、拓展#xff1a;先遍历物品后遍历背包vs先遍历背包后遍历物品先遍历物品后遍历背包#xff08;组合问题… 文章目录 一、题目二、题解方法一完全背包问题的变体版本1方法二完全背包问题变体版本2 三、拓展先遍历物品后遍历背包vs先遍历背包后遍历物品先遍历物品后遍历背包组合问题先遍历背包后遍历物品排列问题 一、题目
给你一个整数数组 coins 表示不同面额的硬币另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额返回 0 。
假设每一种面额的硬币有无限个。
题目数据保证结果符合 32 位带符号整数。
示例 1
输入amount 5, coins [1, 2, 5]
输出4
解释有四种方式可以凑成总金额
55
5221
52111
511111示例 2
输入amount 3, coins [2]
输出0
解释只用面额 2 的硬币不能凑成总金额 3 。示例 3
输入amount 10, coins [10]
输出1提示
1 coins.length 3001 coins[i] 5000coins 中的所有值 互不相同0 amount 5000
二、题解
方法一完全背包问题的变体版本1
题目理解
这道题目是一个动态规划问题需要计算凑成总金额的硬币组合数。给定一组硬币的面额数组 coins 和一个总金额 amount要求计算有多少种不同的组合方式来凑成总金额。每个硬币的面额都可以被使用无限次。
动态规划思路
我们可以将硬币问题与完全背包问题联系起来
将硬币的面额视为物品的重量。将总金额视为背包的容量。将计算硬币组合数的问题视为在完全背包问题中计算组合数量的变种。
定义状态
我们需要定义一个状态来表示问题的子问题和最优解。在这个问题中我们可以使用二维数组 dp[i][j] 来表示前 i 种硬币组成总金额 j 的组合数。其中i 表示考虑的硬币种类数量j 表示总金额。
初始化状态
我们需要初始化状态数组 dp确保其初始值是正确的。在这里可以看到 dp[i][0] 应该初始化为0因为没有硬币可供选择。当 i % coins[0] 0时dp[0][i] 应该初始化为1因为i可以由整数个第一个硬币组成。
状态转移方程
接下来我们需要找到状态之间的转移关系即如何从子问题的最优解推导出原问题的最优解。在这个问题中状态转移方程如下
如果当前总金额 j 小于硬币面额 coins[i]则无法将硬币 i 加入组合所以 dp[i][j] dp[i-1][j]表示不使用硬币 i。如果 j 大于等于硬币面额 coins[i]我们可以选择使用硬币 i 或者不使用。因此dp[i][j] 等于两者之和 不使用硬币 i即 dp[i-1][j]。使用硬币 i即 dp[i][j - coins[i]]这里的 dp[i][j - coins[i]] 表示在考虑硬币 i 时总金额减去硬币 i 的面额后的组合数。
填充状态表格
通过上述状态转移方程我们可以通过双重循环遍历所有的子问题从而填充状态表格 dp。外层循环遍历硬币种类 i内层循环遍历总金额 j根据状态转移方程更新 dp[i][j]。
获取最终答案
最后我们可以通过 dp[coins.size() - 1][amount] 来获取问题的最终答案即考虑了所有硬币种类并且总金额为 amount 时的组合数。
代码解析
class Solution {
public:int change(int amount, vectorint coins) {vectorvectorint dp(coins.size(), vectorint(amount 1, 0));for (int i 0; i amount; i) {if (i % coins[0] 0) {dp[0][i] 1;}}for (int i 1; i coins.size(); i) {for (int j 0; j amount; j) {if (j coins[i]) {dp[i][j] dp[i - 1][j];} else {dp[i][j] dp[i - 1][j] dp[i][j - coins[i]];}}}return dp[coins.size() - 1][amount];}
};创建一个二维数组 dp其中 dp[i][j] 表示前 i 种硬币组成总金额 j 的组合数。 初始化 dp[0][j]即考虑只有一种硬币时对应总金额 j 的组合数。如果 j 可以被第一种硬币整除那么 dp[0][j] 初始化为1表示有一种组合方式即只使用第一种硬币。 通过嵌套的循环遍历硬币种类 i 和总金额 j根据状态转移方程更新 dp[i][j]。如果 j 小于硬币面额 coins[i]则 dp[i][j] 等于 dp[i-1][j]否则 dp[i][j] 等于 dp[i-1][j] dp[i][j - coins[i]]。 最后返回 dp[coins.size() - 1][amount]即考虑了所有硬币种类并且总金额为 amount 时的组合数。
方法二完全背包问题变体版本2
定义状态
首先我们需要定义一个状态来表示问题的子问题和最优解。在这个问题中我们可以使用一维数组 dp其中 dp[i] 表示总金额 i 的组合方式数量。
初始化状态
接下来我们需要初始化状态数组 dp确保其初始值是正确的。在这里可以看到 dp[0] 应该初始化为1因为总金额为0时只有一种组合方式那就是什么硬币都不选。
状态转移方程
然后我们需要找到状态之间的转移关系即如何从子问题的最优解推导出原问题的最优解。状态转移方程如下
对于每个硬币面额 coins[i]我们可以选择使用该硬币或不使用。如果我们选择使用硬币 coins[i]那么 dp[j] 应该等于 dp[j] dp[j - coins[i]]表示在考虑硬币 coins[i] 时总金额 j 的组合方式数量应该加上总金额 j - coins[i] 的组合方式数量。如果我们选择不使用硬币 coins[i]那么 dp[j] 保持不变。
填充状态数组
通过上述状态转移方程我们可以通过循环遍历所有的子问题从而填充状态数组 dp。外层循环遍历硬币的面额 i内层循环遍历总金额 j根据状态转移方程更新 dp[j]。
获取最终答案
最后我们可以通过 dp[amount] 来获取问题的最终答案即总金额为 amount 时的组合方式数量。
代码解析
class Solution {
public:int change(int amount, vectorint coins) {vectorint dp(amount1,0);dp[0] 1;for(int i 0; i coins.size(); i){for(int j coins[i]; j amount; j){dp[j] dp[j-coins[i]];}}return dp[amount];}
};创建一个一维数组 dp其中 dp[i] 表示总金额 i 的组合方式数量。 初始化 dp[0] 为1因为总金额为0时只有一种组合方式即不选硬币。 通过嵌套的循环遍历硬币面额 coins[i] 和总金额 amount根据状态转移方程 dp[j] dp[j - coins[i]] 来更新 dp[j]。这表示在考虑硬币 coins[i] 时总金额 j 的组合方式数量应该加上总金额 j - coins[i] 的组合方式数量。 最后返回 dp[amount]即总金额为 amount 时的组合方式数量。
二维数组版本
class Solution {
public:int change(int amount, vectorint coins) {vectorvectorint dp(coins.size(), vectorint(amount 1, 0));// 初始化第一行当金额为0时有1种方式即不选择任何硬币for (int i 0; i coins.size(); i) {dp[i][0] 1;}for (int i 0; i coins.size(); i) {for (int j 1; j amount; j) {// 如果当前硬币面值大于金额j则不能选择当前硬币直接继承上一种方式的数量if (coins[i] j) {if (i 0) {dp[i][j] dp[i - 1][j];}} else {// 否则可以选择当前硬币或不选择当前硬币if (i 0) {dp[i][j] dp[i - 1][j] dp[i][j - coins[i]];} else {dp[i][j] dp[i][j - coins[i]];}}}}return dp[coins.size() - 1][amount];}
};
三、拓展先遍历物品后遍历背包vs先遍历背包后遍历物品
先遍历物品后遍历背包组合问题
如果我们选择先遍历物品后遍历背包那么我们的状态 dp[j] 表示的是总金额为 j 时的硬币组合数量。在这种情况下我们考虑了每个硬币并决定是否将其放入组合。这导致了我们计算的是硬币的组合数量而不考虑硬币的排列顺序。
#include iostream
#include vector
using namespace std;class Solution {
public:int change(int amount, vectorint coins) {vectorint dp(amount 1, 0); // 初始化动态规划数组dp[i] 表示凑成金额 i 的方法数dp[0] 1; // 凑成金额为 0 的方法数为 1因为什么都不选也是一种方法for (int i 0; i coins.size(); i) {int coin coins[i];for (int j coin; j amount; j) {// 如果当前硬币面额小于等于当前金额 j可以考虑将该硬币加入方案// 当前 dp[j] 的值应该加上 dp[j-coin]表示不使用这个硬币时的方法数dp[j] dp[j - coin];}// 输出当前填写后的 dp 数组cout Coins: coin | DP Array: ;for (int k 0; k amount; k) {cout dp[k] ;}cout endl;}return dp[amount]; // 返回凑成目标金额的方法数}
};int main() {Solution s;vectorint coins { 1, 2, 5 };int amount 5;int result s.change(amount, coins);cout Result: result endl;return 0;
} [注意]大多数格子由三行组成第一行是推导出结果的公式第三行是推导出的结果第二行是组合方式。 先遍历背包后遍历物品排列问题
如果我们选择先遍历背包后遍历物品那么我们的状态 dp[j] 表示的是总金额为 j 时的硬币排列数量。在这种情况下我们考虑了每个背包容量然后决定放入哪些硬币。这导致了我们计算的是硬币的排列数量考虑了硬币的顺序。
注意我写了两个版本一个是一维数组一个是二维数组最直观的就是展现成二维数组。
一维数组
#include iostream
using namespace std;
#include vectorclass Solution {
public:int change(int amount, vectorint coins) {vectorint dp(amount 1, 0);dp[0] 1;for (int j 0 ; j amount; j) {for (int i 0; i coins.size(); i) {if(j coins[i]) dp[j] dp[j - coins[i]];}}return dp[amount];}
};int main()
{Solution s;vectorint coins;coins.push_back(1); coins.push_back(2); coins.push_back(5);int result;result s.change(5, coins);cout result: result endl;
}二维数组 下面这段代码中dp[j][i]的意义是背包为j大小时最后一个放入价值为coins[i]硬币加上不放入该硬币最后一个投入的硬币是从coins[0]到coins[i]之间的硬币的方法种类总数。
#include iostream
#include vector
using namespace std;class Solution {
public:int change(int amount, vectorint coins) {vectorvectorint dp(amount1,vectorint(coins.size(),0)); dp[0][0] 1; int j 0;for (j 0; j amount ; j) {for (int i 0; i coins.size(); i) {if( i 0 ) dp[j][i] dp[j][i - 1];if (j coins[i]) {dp[j][i]dp[j - coins[i]][coins.size() - 1];} }// 输出当前填写后的 dp 数组cout j容量 j | DP Array: ;for (int k 0; k coins.size(); k) {cout dp[j][k] ;}cout endl;}return dp[amount][coins.size()-1]; // 返回凑成目标金额的方法数}
};int main() {Solution s;vectorint coins { 1, 2, 5 };int amount 5;int result s.change(amount, coins);cout Result: result endl;return 0;
} [注意]大多数格子由三行组成第一行是推导出结果的公式第三行是推导出的结果第二行是排列方式。 转置这个矩阵如果看上面矩阵不顺眼
#include iostream
#include vector
using namespace std;class Solution {
public:int change(int amount, vectorint coins) {vectorvectorint dp(coins.size(), vectorint(amount 1, 0));dp[0][0] 1;int i 0;for (i 0; i amount; i) {for (int j 0; j coins.size(); j) {if (j 0) dp[j][i] dp[j-1][i];if (i coins[j]) {dp[j][i] dp[coins.size()-1][i-coins[j]];}}}for (int i 0; i coins.size(); i) {for (int j 0; j amount; j) {cout dp[i][j] ;}cout endl;}return dp[coins.size() - 1][amount]; // 返回凑成目标金额的方法数}
};int main() {Solution s;vectorint coins { 1, 2, 5 };int amount 5;int result s.change(amount, coins);cout Result: result endl;return 0;
}
