搬瓦工如何搭建做网站,高大上的企业网站,网站建设高级,中国能源建设集团网站群Day45代码随想录
322.零钱兑换
1.题目描述
给你一个整数数组 coins #xff0c;表示不同面额的硬币#xff1b;以及一个整数 amount #xff0c;表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额#xff0c;返回 -…Day45代码随想录
322.零钱兑换
1.题目描述
给你一个整数数组 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 121 coins[i] 231 - 10 amount 104
2.解题思路及代码实现
本题注意是最少的组合数那么dp[j]就代表总额为j所能代表的最少组合数量如果dp[j-coins[i]]存在那么递推公式为dp[j] Math.min(dp[j],dp[j-coins[i]]1);
class Solution {public int coinChange(int[] coins, int amount) {int[] dp new int[amount1];for (int i 0; i amount; i) {dp[i] Integer.MAX_VALUE;}dp[0] 0;for (int i 0; i coins.length; i) {for (int j coins[i]; j amount; j) {if (dp[j-coins[i]]!Integer.MAX_VALUE)dp[j] Math.min(dp[j],dp[j-coins[i]]1);}}return dp[amount]Integer.MAX_VALUE ? -1:dp[amount];}
}279.完全平方数
1.题目描述
给你一个整数 n 返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数其值等于另一个整数的平方换句话说其值等于一个整数自乘的积。例如1、4、9 和 16 都是完全平方数而 3 和 11 不是。
示例 1
输入n 12
输出3
解释12 4 4 4示例 2
输入n 13
输出2
解释13 4 9提示
1 n 104
2.解题思路及代码实现
其实本题和零钱兑换思路一样
class Solution {public int numSquares(int n) {int[] dp new int[n1];for (int i 0; i n ; i) {dp[i] Integer.MAX_VALUE;}dp[0] 0;for (int i 1; i (int)Math.sqrt(n); i) {int amount i*i;for (int j amount; j n ; j) {if (dp[j-amount]! Integer.MAX_VALUE)dp[j] Math.min(dp[j],dp[j-amount]1);}}return dp[n];}
}
