SHARE
TWEET

Untitled

ogv Nov 18th, 2019 78 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2.     public int change(int amount, int[] coins) {                
  3.         int[] dp = new int[amount + 1];        
  4.         dp[0] = 1;
  5.        
  6.         for (int coin: coins)
  7.             for (int n = coin; n <= amount; n++)
  8.                 dp[n] += dp[n - coin];        
  9.        
  10.         return dp[amount];
  11.     }
  12. }
  13.  
  14. class Solution {
  15.     public int change(int amount, int[] coins) {
  16.         return change(amount, coins.length - 1, coins, new int[coins.length][amount + 1]);
  17.     }
  18.    
  19.     private int change(int amount, int k, int[] coins, int[][] cache) {        
  20.         if (amount == 0)  return 1;
  21.         if (k == -1) return 0;
  22.                
  23.         if (cache[k][amount] != 0) return cache[k][amount] - 1;
  24.        
  25.         int result = change(amount, k - 1, coins, cache);
  26.         if (amount >= coins[k]) {
  27.             result += change(amount - coins[k], k, coins, cache);
  28.         }                
  29.        
  30.         cache[k][amount] = result + 1;
  31.         return result;
  32.     }
  33. }
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
 
Top