动态规划之硬币问题

 其实动态规划对于我最难的是边界问题

动态规划四部曲：

1.确定状态，确定从什么时候开始，就是amout

2.确定转移方程，也就是 if (coins[j] <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);//变成子问题，问题规模缩小
                }

3.确定初始条件和边界条件，也就是前面和后面几步

4.确定步数和尝试次数，也就是i和j的范围

class Solution {
    public int coinChange(int[] coins, int amount) {
        int max = amount + 1;//设置max填充dp数列，为之后的边界问题做铺垫
        int[] dp = new int[amount + 1];//定义dp长度，因为dp是从1开始，所以需要多一格
      
        Arrays.fill(dp, max);//填充数列
       
        dp[0] = 0;//dp[0]设置值，为特殊情况做准备
      
        for (int i = 1; i <= amount; i++) {//一步步递进
            for (int j = 0; j < coins.length; j++) {
                if (coins[j] <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);//变成子问题，问题规模缩小
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];//判断是否正好组成总金额
    }
}