SHARE
TWEET

Untitled

a guest Sep 21st, 2019 78 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.HashMap;
  2.  
  3. class Solution {
  4.     HashMap<Integer, HashMap> memo;
  5.     int[] coins;
  6.     int array_sum;
  7.    
  8.     public int coinChange(int[] coins, int amount) {
  9.         this.coins = coins;
  10.         this.memo = new HashMap<Integer, HashMap>();
  11.         for (int i = 0; i < coins.length; ++i) array_sum += coins[i];
  12.         int return_val = dp(0, amount);
  13.         return (return_val == array_sum + 1) ? -1 : return_val;
  14.     }
  15.    
  16.     public int dp(int idx, int amount)  {
  17.         if (memo.containsKey(idx))  {
  18.             HashMap<Integer, Integer> hm = memo.get(idx);
  19.             if (hm.containsKey(amount))  {
  20.                 return hm.get(amount);
  21.             }
  22.         }
  23.         if (amount == 0) return 0;
  24.         if (amount < 0 || idx == coins.length) return array_sum + 1;
  25.        
  26.         int take_coin = 1 + dp(idx, amount - coins[idx]);
  27.         int leave_coin = dp(idx+1, amount);
  28.         int return_val = Math.min(take_coin, leave_coin);
  29.         if (!memo.containsKey(idx)) {
  30.             memo.put(idx, new HashMap<Integer, Integer>());
  31.         }
  32.         HashMap<Integer, Integer> hm = memo.get(idx);
  33.         hm.put(amount, return_val);
  34.         return return_val;
  35.     }
  36. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top