动态规划-零钱兑换

零钱兑换也是动态规划的典型问题，一般是给你几种零钱，数量不限，给一个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];