5.找零钱

$dp[i] = Math.min(dp[i], dp[i - coin] + 1);$

• 2.18

  • if 里判断的是dp[i-coin]，也就是目标不为空才+1

• 2.4

  • 这里满足条件（dp[i-coin]!=Integer.MAX_VALUE）才进行状态转移方程类似与上一题的 j*j<i
  • 不满足条件返回-1

• 12.4

  1. 想到了转移公式,但是忘记了i要从coin数值开始而不是像上一题从1开始(因为最开始就是从coin开始的,不能让他为负下标)
  2. 在**状态转移方程前,先判断是否越界(MAX_VALUE+1等于越界)**了在继续(里面是Max_VALUe说明根本凑不出来!!)
  3. 看题目!如果找不到返回-1!!!!!

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        Arrays.fill(dp,Integer.MAX_VALUE);
        dp[0] = 0;
        for(int coin:coins){
            for(int i=coin;i<=amount;i++){
                if(dp[i-coin]!=Integer.MAX_VALUE){//凑不出来直接下一个
                    dp[i] = Math.min(dp[i],dp[i-coin]+1);
                }
            }
        }
        return dp[amount] == Integer.MAX_VALUE ? -1 :dp[amount];
    }
}

• 先初始化数组(max_value)
• 在遍历硬币数组
• i从coin的面额开始,不然会数组越界比如-2
• 判断硬币
  • (dp[i-coin]!=Integer.MAX_VALUE是看能不能凑出那个硬币,如果凑不出来就是无穷大,凑的出来就说明找到了)
• 在每个硬币品种下进行状态转移公式