刷题第10篇：从完全平方到零钱兑换

public int numSquares(int n) {
    int[] nums = new int[n+1];
    return help(n,nums);
}
public int help(int n, int[] nums){
    if(n == 0) return 0;
    if(nums[n] > 0) return nums[n];

    for(int i = 1 ; n >= i*i ; i++ ){
        int num = help(n - i*i , nums);//获取n-i*i的完全平方数
        if(num >= 0 && nums[n] > 0) nums[n] = Math.min(nums[n] , num +1);
        if(num >= 0 && nums[n] == 0) nums[n] = num+1;//初始化
    }
    return nums[n];
}

for(int i = 1 ; n >= i*i ; i++ )

for(int coin:coins)

public int coinChange(int[] coins, int amount) {
    int len = coins.length;
    if(len == 0) return 0;
    return coinChange(coins,amount,new int[amount+1]);
}
public int coinChange(int[] coins, int amount,int[] nums) {
    if(amount < 0) return -1;
    if(amount == 0) return 0;
    if(nums[amount] != 0) return nums[amount];
    //寻找上一个
    for(int coin:coins){
        int res = coinChange(coins,amount-coin,nums);//得到amount-coin的数量
        if(res >= 0 && nums[amount] > 0) nums[amount] = Math.min(nums[amount] , res+1);//比较更新最小值
        if(res >= 0 && nums[amount] == 0) nums[amount] = res+1;//赋初始值
    }
    if(nums[amount] == 0) nums[amount] = -1;
    return nums[amount];
}