• API
• FAQ
• Tools
• Archive
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.
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!

Top