零钱兑换也是动态规划的典型问题,一般是给你几种零钱,数量不限,给一个amount,问共有多少种兑零钱的方法。
我们看一个案例
案例1:
给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1 。
你可以认为每种硬币的数量是无限的。
我们首先定义一个dp数组,dp[i]表示兑换i块钱所需的最少硬币个数。
加入coins={1,2,5}
那么dp[i]就可以拆分为三个小问题
①dp[i-1]+1
②dp[i-2]+1
③dp[i-5]+1
因为要求的是最少硬币个数,所有我们对三种方案求最小值即可。
class Solution { public int coinChange(int[] coins, int amount) { int max = amount + 1; int[] dp = new int[amount + 1]; //根据题意,可能有兑换不成功的情况,所以我们定义dp[i]的最大值为amount+1 Arrays.fill(dp, max); dp[0] = 0; for (int i = 1; i <= amount; i++) { for (int j = 0; j < coins.length; j++) { //只有当前钱数i大于硬币面值时才可以兑换 int coin=coins[j]; if (coin <= i) { dp[i] = Math.min(dp[i], dp[i - coin] + 1); } } } return dp[amount] > amount ? -1 : dp[amount]; } }
案例2:给你一个由 不同 整数组成的数组 nums ,和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
题目数据保证答案符合 32 位整数范围。
这个题目和案例1极为相似,差别在于案例1求的是最小硬币个数,本题目求的是组合个数
public int combinationSum4(int[] nums, int target) { int[] dp = new int[target + 1]; dp[0] = 1; //对应任意x,dp[x],如果有nums[i]小于x,那么dp[x]=sum{dp[x-nums[i]]} for (int i = 1; i <= target; i++) { for (int num : nums) { if (num <= i) { dp[i] += dp[i - num]; } } } return dp[target];
原文地址:http://www.cnblogs.com/wangbin2188/p/16848332.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性