35互联做网站多少钱,广东省网站设计与开发,物联网工程专业,结构设计师之家官网题目链接
零钱兑换
题目描述 注意点
如果没有任何一种硬币组合能组成总金额#xff0c;返回 -1可以认为每种硬币的数量是无限的
解答思路
动态规划从总金额1开始推出目标金额所需的最少硬币个数#xff0c;任意某个金额所需的最少硬币个数可以由当前金额减去每种面额的硬…题目链接
零钱兑换
题目描述 注意点
如果没有任何一种硬币组合能组成总金额返回 -1可以认为每种硬币的数量是无限的
解答思路
动态规划从总金额1开始推出目标金额所需的最少硬币个数任意某个金额所需的最少硬币个数可以由当前金额减去每种面额的硬币通过前置金额所需的最少硬币个数加1就是当前金额所需的最少硬币个数
代码
class Solution {public int coinChange(int[] coins, int amount) {int[] dp new int[amount 1];for (int i 1; i amount; i) {int minNum -1;for (int coin : coins) {if (i - coin 0 || dp[i - coin] 0) {continue;}minNum minNum 0 ? dp[i - coin] : Math.min(minNum, dp[i - coin]);}dp[i] minNum 0 ? minNum : (minNum 1);}return dp[amount];}
}关键点
动态规划的思想
