网站做支付宝支付需要哪些资料,集团网站开发,阿里巴巴上面可以做网站,广东智慧团建系统入口题目
与01背包的区别就是可以重复拿一件物品 零钱兑换 给你一个整数数组 coins #xff0c;表示不同面额的硬币#xff1b;以及一个整数 amount #xff0c;表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额#xff…题目
与01背包的区别就是可以重复拿一件物品 零钱兑换 给你一个整数数组 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] 231 - 1 0 amount 104
题解
记忆化搜索
class Solution {private int[] coins;private int[][] cache;public int coinChange(int[] coins, int amount) {this.coins coins;int n coins.length;cache new int[n][amount 1];for (int i 0; i n; i) {Arrays.fill(cache[i],-1);// -1表示曾经没遍历过}int ans dfs(n - 1,amount);return ans Integer.MAX_VALUE / 2 ? ans : -1;}private int dfs(int i, int c) {if (i 0) {return c 0 ? 0 : Integer.MAX_VALUE / 2;// 除以2防止溢出}if (cache[i][c] ! -1) {return cache[i][c];}if (c coins[i]) {return cache[i][c] dfs(i - 1, c);} return cache[i][c] Math.min(dfs(i - 1,c),dfs(i,c-coins[i]) 1);}
}递推
class Solution {public int coinChange(int[] coins, int amount) {int n coins.length;int[][] f new int[n1][amount1];Arrays.fill(f[0], Integer.MAX_VALUE / 2);f[0][0] 0;for (int i 0; i n; i) {for (int c 0; c amount; c) {if (c coins[i]) {f[i 1][c] f[i][c];} else {f[i 1][c] Math.min(f[i][c],f[i 1][c - coins[i]] 1);}}}int ans f[n][amount];return ans Integer.MAX_VALUE / 2 ? ans : -1;}
}一个数组
class Solution {public int coinChange(int[] coins, int amount) {int[] f new int[amount 1];Arrays.fill(f, Integer.MAX_VALUE / 2);f[0] 0;for (int x : coins) {for (int c x; c amount; c) {f[c] Math.min(f[c], f[c - x] 1);}}int ans f[amount];return ans Integer.MAX_VALUE / 2 ? ans : -1;}
}
