I used @Jerry's idea, and made 2 small changes. 16ms, beats 98%.

checks overflow problem. makes dp array to initialize to MAX_VALUE, since there are no guarantee that one dollar will necessarily appear. ( I am assuming that his idea is there are at least ONE-dollar coin. Feel free to correct me if I am wrong.) class Solution { public int coinChange(int[] coins, int amount) { int[] dp = new int[amount + 1]; // initialize to maximum value for (int i = 0; i < dp.length; i++) dp[i] = Integer.MAX_VALUE; dp[0] = 0; // put this at outer loop to (possibly) avoid some dp slots for (int coin : coins) for(int i = coin ;i < dp.length ; i++) // check on possible overflow problem if(dp[i-coin] != Integer.MAX_VALUE) dp[i] = Math.min(dp[i], dp[i - coin] + 1); // if bigger -> still Max_Value -> not possible return dp[amount] > amount ? -1 : dp[amount]; } }Coin Change