【算法挨揍日记】day44——518. 零钱兑换 II、279. 完全平方数
2024-01-03 12:28:34
?518. 零钱兑换 II
题目描述:
给你一个整数数组?coins
?表示不同面额的硬币,另给一个整数?amount
?表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回?0
?。
假设每一种面额的硬币有无限个。?
题目数据保证结果符合 32 位带符号整数。
解题思路:
算法思路:
先将问题「转化」成我们熟悉的题型。
i.
在?些物品中「挑选」?些出来,然后在满?某个「限定条件」下,解决?些问题,?概率
是背包模型;
ii.
由于每?个物品都是?限多个的,因此是?个「完全背包」问题。
接下来的分析就是基于「完全背包」的?式来的。
1.
状态表?:
dp[i][j]
表?:从前
i
个硬币中挑选,总和正好等于
j
,?共有多少种选法。
2.
状态转移?程:
线性
dp
状态转移?程分析?式,?般都是「根据最后?步」的状况,来分情况讨论。但是最后
?个物品能选很多个,因此我们的需要分很多情况:
i.
选
0
个第
i
个硬币:此时相当于就是去前
i - 1
个硬币中挑选,总和正好等于
j
。
此时最少的硬币个数为
dp[i - 1][j]
;
ii.
选
1
个第
i
个硬币:此时相当于就是去前
i - 1
个硬币中挑选,总和正好等于
j -
v[i]
。因为挑选了?个
i
硬币,此时最少的硬币个数为
dp[i - 1][j -
coins[i]] + 1
;
ii.
选
2
个第
i
个硬币:此时相当于就是去前
i - 1
个硬币中挑选,总和正好等于
j
- 2 * coins
。因为挑选了两个
i
硬币,此时最少的硬币个数为
dp[i - 1][j -
2 * coins[i]] + 2
;
iv.
......
结合我们在完全背包??的「优化思路」,我们最终得到的状态转移?程为:
dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i]] + 1
。
这?教给?家?个技巧,就是相当于把第?种情况
dp[i - 1][j - coins[i]] + 1
?
?的
i - 1
变成
i
即可。
3.
初始化:
初始化第??即可。
第??表?没有物品,没有物品正好能凑能和为
0
的情况。因此
dp[0][0] = 1
,其余位置都
是
0
种情况。
4.
填表顺序:
根据「状态转移?程」,我们仅需「从上往下」填表即可。
5.
返回值:
根据「状态表?」,返回
dp[n][V]
。
解题思路:
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. 完全平方数
题目描述:
给你一个整数?n
?,返回?和为?n
?的完全平方数的最少数量?。
完全平方数?是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,1
、4
、9
?和?16
?都是完全平方数,而?3
?和?11
?不是。
解题思路:
算法思路:
这?给出?个?「拆分出相同?问题」的?式,定义?个状态表?。(?「完全背包」?式的解法
就仿照之前的分析模式就好啦~~)
为了叙述?便,把和为
n
的完全平?数的最少数量简称为「最?数量」。
对于
12
这个数,我们分析?下如何求它的最?数量。
?
如果
12
本?就是完全平?数,我们不?算了,直接返回
1
;
?
但是
12
不是完全平?数,我们试着把问题分解?下:
1.
情况?:拆出来?个
1
,然后看看
11
的最?数量,记为
x1
;
2.
情况?:拆出来?个
4
,然后看看
8
的最?数量,记为
x2
;(为什么拆出来
4
,
?不拆出来
2
呢?)
3.
情况三:拆出来?个
8
......
其中,我们接下来求
11
、
8
的时候,其实?回到了原来的问题上。
因此,我们可以尝试?
dp
的策略,将
1 2 3 4 6
等等这些数的最?数量依次保存起来。再求
较?的
n
的时候,直接查表,然后找出最?数量。
1.
状态表?:
dp[i]
表?:和为
i
的完全平?数的最少数量。
2.
状态转移?程:
对于
dp[i]
,根据思路那?的分析我们知道,可以根据?于等于
i
的所有完全平?数
x
进?
划分:
?
x = 1
时,最?数量为:
1 + dp[i - 1]
;
?
x = 4
时,最?数量为:
1 + dp[i - 4]
......
?直枚举到
x <= i
为?。
为了?便枚举完全平?数,我们采?下?的策略:
for(int j = 1; j * j <= i; j++)
综上所述,状态转移?程为:
dp[i] = min(dp[i], dp[i - j * j] + 1)
3.
初始化:
当
n = 0
的时候,没法拆分,结果为
0
;
当
n = 1
的时候,显然为
1
。
4.
填表顺序:
从左往右。
5.
返回值:
根据题意,返回
dp[n]
的值。
解题代码:
class Solution {
public:
int numSquares(int n) {
vector<int> dp(n + 1);
dp[1] = 1; // 初始化
for (int i = 2; i <= n; i++) // 枚举每个数
{
dp[i] = 1 + dp[i - 1]; // ?少等于 1 + dp[i - 1]
for (int j = 2; j * j <= i; j++) // ??于 i 的完全平?数划分区间
dp[i] =
min(dp[i], dp[i - j * j] + 1); // 拿到所有划分区间内的最?值
}
// 返回结果
return dp[n];
}
};
”
文章来源:https://blog.csdn.net/m0_69061857/article/details/135340634
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!