零钱兑换(动态规划)

给你一个整数数组 coins ，表示不同面额的硬币；每种硬币的数量无限；以及一个整数 amount ，表示总金额，问最少需要几枚硬币凑出这个金额，如果没有任何一种硬币组合能组成总金额，返回 -1 。

例如 N = 3，面值分别为 1，2，5，总金额 amount = 11。那么最少需要 3 枚硬币凑出，即 11 = 5 + 5 + 1。

首先，这个问题是动态规划问题，因为它具有「最优子结构」的。要符合「最优子结构」，子问题间必须互相独立。

为什么符合最优子结构? 假设有面值为 1, 2, 5 的硬币，求 amount = 11 时的最少硬币数（原问题），如果你知道凑出 amount = 10, 9, 6 的最少硬币数（子问题），只需要把子问题的答案加一（再选一枚面值为 1, 2, 5 的硬币），求个最小值，就是原问题的答案。因为硬币的数量是没有限制的，所以子问题之间没有相互制，是互相独立的。

然后根据动态规划问题, 列出正确的状态转移方程:

1.base case (amount为0时,算法返回0)

2.state (原问题和子问题中会变化的变量) 硬币数量无限，硬币的面额也是题目给定的，只有目标金额会不断地向 base case 靠近，所以唯一的「状态」就是目标金额 amount

3.choice (导致状态产生变化 )每选择一枚硬币，就相当于减少了目标金额

4.dp (函数/数组的定义 ) 一个递归的 dp 函数, 函数的参数就是状态转移中会变化的量

dp(n) 表示，输入一个目标金额 n，返回凑出目标金额 n 所需的最少硬币数量。

解法伪代码

int coinChange(int[]coins,int amount){
    return dp(coins,amount)
}

// 定义：要凑出金额 n，至少要 dp(coins, n) 个硬币
int dp(int[] coins, int n) {
    // 选择需要硬币最少的那个结果
    for (int coin : coins) {
        result = min(res, 1 + dp(n - coin))
    }
    return result
}

class Solution {
    public int coinChange(int[] coins, int amount) {
        if(amount == 0) return 0;
        if(amount<=0) return -1;
        int[] dp = new int[amount+1];
        Arrays.fill(dp,amount+1);
        dp[0] = 0;
        for(int coin:coins){
            for(int i = coin; i <= amount; i++){
                dp[i] = Math.min(dp[i],dp[i-coin]+1);
            }
        }

        return dp[amount]==amount+1?-1:dp[amount];
    }
}