LeetCode 训练场：322. 零钱兑换

public int coinChange(int[] coins, int amount) {
    // base case
    if(amount == 0){
        return 0;
    }

    // 数组大小为 amount + 1
    int[] dp = new int[amount + 1];

    // 外层循环在遍历所有状态的所有取值
    for(int i = 1; i <= amount; i++){

        // 数组初始值也为 amount + 1
        dp[i] = amount + 1;

        // 内层循环循环求所有选择的最小值
        for(int coin: coins){
            if(i >= coin){
                // 状态方程
                dp[i] = Math.min(dp[i-coin] + 1, dp[i]);
            }
        }
    }

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