322. 零钱兑换

image.png

解题思路

自下而上的解决问题
dp[amount]代表总数是amount的钱，需要硬币的最小个数
Arrays.fill(dp,amount+1);将dp数组初始化为amount+1，这个并不是绝对的，你随时可以修改这个值

image.png

图中的f和dp等价
要算第i项，需要对前i-1项计算，得出结果
举例说明
计算钱数为a的最小硬币数，假设选其中一枚硬币，选之前的最小硬币数+1就是要求的结果

image.png
同理：
如果dp[amount] > amount，就说明肯定不能凑齐啊，因为硬币数咋可能比钱数还多呢？

代码

class Solution {
    public int coinChange(int[] coins, int amount) {
         int [] dp=new int[amount+1];
        Arrays.fill(dp,amount+1);//初始化，最小为amount+1，因为如果无法构成，dp[amount]必为amount+1，即一定为初始///值，只有初始化为amount+1,这样才能大于amount
         dp[0]=0;
         for(int i=1;i<=amount;i++){
             for(int j=0;j<coins.length;j++){
                 if(i>=coins[j]) dp[i]=Math.min(dp[i],dp[i-coins[j]]+1);
             }
         }
         return dp[amount] > amount ? -1 : dp[amount];
    }
}