【Hot100】LeetCode—322. 零钱兑换
[*]原题链接：322. 零钱兑换
1- 思路
动态规划
动规五部曲
[*]1- 定义 dp 数组确定含义
[*]dp 代表凑到款项为 j 的最少硬币个数
[*]2- 递推公式
[*]dp = Math.min(dp,dp+1)
[*]3- 初始化
[*]dp = 0
[*]其他全部初始化为 max
[*]4- 遍历序次
[*]先遍历物品，再遍历背包
[*]递推过程需要判断 dp] != max
2- 实现
⭐322. 零钱兑换——题解思路
https://i-blog.csdnimg.cn/direct/b984f7c8fc3841ee8e89e747c7b5756c.png
class Solution {
public int coinChange(int[] coins, int amount) {
// 1. 定义 dp 数组
// dp 代表凑到金钱为 j 的最少硬币个数
int[] dp = new int;
// 2.递推公式
// dp = Math.min(dp,dp+1)
// 初始化
dp = 0;
int max = Integer.MAX_VALUE;
for(int i = 1 ; i <= amount;i++){
dp = max;
}
// 4. 遍历顺序
// 物品
for(int i = 0 ; i < coins.length;i++){
for(int j = coins ; j <= amount ; j++){
if(dp] != max){
dp = Math.min(dp,dp]+1);
}
}
}
if(dp==max){
return -1;
}
return dp;
}
}
3- ACM 实现
public class minCoins {
public static int minCoins(int[] nums,int target){
// 定义 dp
int[] dp = new int;
// 2. 递推公式
// dp = Math.min(dp,dp]+1);
// 3.初始化
dp = 0;
int max = Integer.MAX_VALUE;
for(int i = 1 ; i <= target;i++){
dp = max;
}
// 4.遍历顺序
for(int i = 0 ; i <nums.length;i++){
for(int j = nums; j<=target;j++){
if(dp] != max){
dp = Math.min(dp,dp]+1);
}
}
}
if(dp==max){
return -1;
}
return dp;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String input = sc.nextLine();
String[] parts = input.split(" ");
int[] nums = new int;
for(int i = 0 ; i < parts.length;i++){
nums = Integer.parseInt(parts);
}
int target = sc.nextInt();
System.out.println("结果是"+minCoins(nums,target));
}
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]