Leetcode #518
Yet another Dynamic Programming problem. I’ve really got to brush up on this, especially being able to identify when to use top-down memoization vs bottom-up tabulation. This, however isn’t the optimal solution though.
Problem
You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.
Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return 0.
You may assume that you have an infinite number of each kind of coin.
The answer is guaranteed to fit into a signed 32-bit integer.
Example 1:
Input: amount = 5, coins = [1,2,5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
Example 2:
Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.
Example 3:
Input: amount = 10, coins = [10]
Output: 1
Constraints:
1 ⇐ coins.length ⇐ 300
1 ⇐ coins[i] ⇐ 5000
All the values of coins are unique.
0 ⇐ amount ⇐ 5000
My Solution (Bottom-Up Tabulation)
class Solution {
public int change(int amount, int[] coins) {
/*
- DP: Bottom Up Tabulation
- len = coins.length
- dp[len+1][amount+1]
- dp[i][a]: number of ways to make amount a
using only the first i coins
- dp[i][0] = 1
- for each coin : ith coin: coins[i-1]
- for each amount:
- combis without coin + combis w coin
- dp[i-1][a] + dp[i][a-coin]
*/
int len = coins.length;
int[][] dp = new int[len+1][amount+1];
// 1 way to make $0 for all
for (int i = 0; i < len+1; i++) {
dp[i][0] = 1;
}
for (int i=1; i<len+1; i++) {
// i-th coin = coins[i-1]
int coin = coins[i-1];
for (int a=1; a<amount+1; a++) {
dp[i][a] = dp[i-1][a];
if (coin <= a) {
dp[i][a] += dp[i][a-coin];
}
}
}
return dp[len][amount];
}
}This isn’t the optimal solution!
