322. Coin Change

动态规划里例题，硬币问题。

p[i] = dp[i - coin[j]] + 1;

注意i < coin[j] dp[i-coin[j]]无解都要跳过。

public class Solution 
{
    public int coinChange(int[] coins, int amount) 
    {
        int[] dp = new int[amount+1];
        Arrays.fill(dp,Integer.MAX_VALUE);
        //dp[i] = dp[i - coin[j]] + 1;
        dp[0] = 0;
        for(int i = 0; i <= amount; i++)
        {
            for(int j = 0; j < coins.length;j++)
            {
                if(i < coins[j] || dp[i-coins[j]] == Integer.MAX_VALUE) continue;

                dp[i] = Math.min(dp[i],dp[i - coins[j]]+1);
            }
        }
        
        
        if(dp[amount] == Integer.MAX_VALUE) return -1;
        else return dp[amount];
    }
}

第一次看到动态规划觉得好神奇。。