本文主要是介绍每日OJ题_完全背包②_力扣322. 零钱兑换,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
目录
力扣322. 零钱兑换
问题解析
解析代码
优化代码(滚动数组)
力扣322. 零钱兑换
322. 零钱兑换
难度 中等
给你一个整数数组 coins
,表示不同面额的硬币;以及一个整数 amount
,表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1
。
你可以认为每种硬币的数量是无限的。
示例 1:
输入:coins = [1, 2, 5], amount = 11输出:3解释:11 = 5 + 5 + 1
示例 2:
输入:coins = [2], amount = 3输出:-1
示例 3:
输入:coins = [1], amount = 0输出:0
提示:
1 <= coins.length <= 12
1 <= coins[i] <= 2^31 - 1
0 <= amount <= 10^4
class Solution {
public:int coinChange(vector<int>& coins, int amount) {}
};
问题解析
先看能不能将问题转化成我们熟悉的题型。
- 在一些物品中挑选一些出来,然后在满足某个限定条件下,解决一些问题,大概率是背包模型;
- 由于每一个物品都是无限多个的,因此是一个完全背包问题。接下来的分析就是基于完全背包的方式来
状态表示: dp[i][j] 表示:从前 i 个硬币中挑选,总和正好等于 j ,所有的选法中,最少的硬币个 数。
状态转移方程:
线性 dp 状态转移方程分析方式,一般都是根据最后一步的状况,来分情况讨论。但是最后一个物品能选很多个,因此需要分很多情况:
- 选 0 个第 i 个硬币:此时相当于就是去前 i - 1 个硬币中挑选,总和正好等于 j 。 此时最少的硬币个数为 dp[i - 1][j]
- 选 1 个第 i 个硬币:此时相当于就是去前 i - 1 个硬币中挑选,总和正好等于 j - v[i] 。因为挑选了一个 i 硬币,此时最少的硬币个数为 dp[i - 1][j - coins[i]] + 1 ;
- 选 2 个第 i 个硬币:此时相当于就是去前 i - 1 个硬币中挑选,总和正好等于 j - 2 * coins 。因为挑选了两个 i 硬币,此时最少的硬币个数为 dp[i - 1][j - 2 * coins[i]] + 2 ;
- ......
综上,状态转移方程为:
dp[i][j]=min(dp[i - 1][j], dp[i - 1][j - coins[i]] + 1, dp[i - 1][j - 2*coins[i]] + 2 ......)
这时发现,计算一个状态的时候,需要一个循环才能搞定的时候,我们要想到去优化。优化的方向就是用一个或者两个状态来表示这一堆的状态,通常就是用数学的方式做一下等价替换。
发现第二维是有规律的变化的,因此去看看 dp[i][j - v[i]] 这个状态: dp[i][j - v[i]]=min(dp[i - 1][j - coins[i]] + 1,dp[i - 1][j - 2*coins[i]]] + 2,dp[i - 1] [j - 3*coins[i]] + 3......)
因此可以修改我们的状态转移方程为: dp[i][j] = min(dp[i - 1][j], dp[i][j - coins[i]] + 1) 。(j >= coins[i] , dp[i][j - coins[i]] 存在 。)(如果初始化多开一行一列,找coins数组要减一)
有个技巧,就是相当于把第二种情况 dp[i - 1][j - coins[i]] + 1 ⾥ ⾯的 i - 1 变成 i 即可。
初始化: dp[0[0]为0,初始化第一行即可。 这里因为取 min ,所以可以把无效的地方设置成无穷大 (0x3f3f3f3f) 因为这里要求正好凑成总和为 j ,因此,需要把第一行除了第一个位置的元素,都设置成无穷大。
填表顺序: 根据状态转移方程,仅需从上往下填表。
返回值: 根据状态表示,返回 dp[n][amount] 。由于最后可能凑不成总数为 amount 的情况,因此返回之前需要特判一下。
解析代码
class Solution {
public:int coinChange(vector<int>& coins, int amount) {const int INF = 0x3f3f3f3f; // 无穷大的一半int n = coins.size();vector<vector<int>> dp(n + 1, vector<int>(amount + 1, INF));// dp[i][j]表示:从前i个硬币中挑选,总和正好等于j,所有的选法中,最少的硬币个数dp[0][0] = 0;for(int i = 1; i <= n; ++i){for(int j = 0; j <= amount; ++j){if(j >= coins[i - 1])dp[i][j] = min(dp[i - 1][j], dp[i][j - coins[i - 1]] + 1);elsedp[i][j] = dp[i - 1][j];}}return dp[n][amount] >= INF ? -1 : dp[n][amount];}
};
优化代码(滚动数组)
背包问题基本上都是利用滚动数组来做空间上的优化:
- 利用滚动数组优化。
- 直接在原始代码上修改。
在完全背包问题中,优化的结果为:
- 仅需删掉所有的横坐标。
(填一行数组的值的时候要用到前面新填的值,所以依旧是从左往右遍历,01背包是从右往左)
class Solution {
public:int coinChange(vector<int>& coins, int amount) {const int INF = 0x3f3f3f3f; // 无穷大的一半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];}
};
这篇关于每日OJ题_完全背包②_力扣322. 零钱兑换的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!