1. 题⽬链接:322. 零钱兑换
2. 题⽬描述:
3. 解法(动态规划):
算法思路:
先将问题「转化」成我们熟悉的题型。
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 ;
iii. 选 2 个第 i 个硬币:此时相当于就是去前 i - 1 个硬币中挑选,总和正好等于 j- 2 * coins 。因为挑选了两个 i 硬币,此时最少的硬币个数为 dp[i - 1][j -2 * coins[i]] + 2 ;
iv. ......
结合我们在完全背包⾥⾯的优化思路,我们最终得到的状态转移⽅程为:
dp[i][j] = min(dp[i - 1][j], dp[i][j - coins[i]] + 1) 。
这⾥教给⼤家⼀个技巧,就是相当于把第⼆种情况 dp[i - 1][j - coins[i]] + 1 ⾥⾯的 i - 1 变成 i 即可。
3. 初始化:
初始化第⼀⾏即可。
这⾥因为取 min ,所以我们可以把⽆效的地⽅设置成⽆穷⼤ (0x3f3f3f3f)
因为这⾥要求正好凑成总和为 j ,因此,需要把第⼀⾏除了第⼀个位置的元素,都设置成⽆穷⼤。
4. 填表顺序:
根据「状态转移⽅程」,我们仅需「从上往下」填表即可。
5. 返回值:
根据「状态表⽰」,返回 dp[n][V] 。但是要特判⼀下,因为有可能凑不到
C++ 优化前的算法代码:
#define N 0x3f3f3f3f
class Solution
{
public:
int coinChange(vector<int>& coins, int amount)
{
//建表
int m=coins.size(),n=amount;
vector<vector<int>>dp(m+1,vector<int>(n+1));
//初始化
for(int i=1;i<=n;i++)
{
dp[0][i]=N;
}
//填表
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
//不选
dp[i][j]=dp[i-1][j];
//选
//因为完全背包此处判断的是dp表同一行的状态
//使得dp[i][j]不存在时也会进入判断,故将选不到的状态定为极大值
if(j-coins[i-1]>=0&&dp[i][j-coins[i-1]]!=N)
{
dp[i][j]=min(dp[i][j],dp[i][j-coins[i-1]]+1);
}
}
}
//返回值
return ((dp[m][n] == N) ? -1 : dp[m][n]);
}
};
C++ 空间优化后的算法代码:
#define N 0x3f3f3f3f
class Solution
{
public:
int coinChange(vector<int>& coins, int amount)
{
//建表
int m=coins.size(),n=amount;
vector<int>dp(n+1);
//初始化
for(int i=1;i<=n;i++)
{
dp[i]=N;
}
//填表
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
//因为完全背包此处判断的是dp表同一行的状态
//使得dp[i][j]不存在时也会进入判断,故将选不到的状态定为极大值
if(j-coins[i-1]>=0&&dp[j-coins[i-1]]!=N)
{
dp[j]=min(dp[j],dp[j-coins[i-1]]+1);
}
}
}
//返回值
return ((dp[n] == N) ? -1 : dp[n]);
}
};
Java 优化前算法代码:
class Solution
{
public int coinChange(int[] coins, int amount)
{
// 1. 创建 dp 表
// 2. 初始化
// 3. 填表
// 4. 返回值
int n = coins.length, INF = 0x3f3f3f3f;
int[][] dp = new int[n + 1][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] = Math.min(dp[i][j], dp[i][j - coins[i - 1]] + 1);
}
return dp[n][amount] >= INF ? -1 : dp[n][amount];
}
}
Java 空间优化后的算法代码:
class Solution
{
public int coinChange(int[] coins, int amount)
{
// 1. 创建 dp 表
// 2. 初始化
// 3. 填表
// 4. 返回值
int n = coins.length, INF = 0x3f3f3f3f;
int[] dp = new int[amount + 1];
for (int j = 1; j <= amount; j++) dp[j] = INF;
for (int i = 1; i <= n; i++)
for (int j = coins[i - 1]; j <= amount; j++)
dp[j] = Math.min(dp[j], dp[j - coins[i - 1]] + 1);
return dp[amount] >= INF ? -1 : dp[amount];
}
}
标签:初始化,硬币,int,coins,amount,零钱,算法,兑换,dp
From: https://blog.csdn.net/2301_79580018/article/details/143613548