forked from TheAlgorithms/Java
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathCoinChange2.java
More file actions
50 lines (32 loc) · 1.25 KB
/
Copy pathCoinChange2.java
File metadata and controls
50 lines (32 loc) · 1.25 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
package DynamicProgramming;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Scanner;
public class CoinChange2{
public static void main(String[] args) throws Exception {
int amount = 12;
int[] coins = {2, 4, 5};
System.out.print(change(amount, coins));
}
// Two key points:
// create memoization with respect to 0 (thus initialize memo with null)
// in a recursive call using index i without increment
// Last key respects cases 1 + 2 == 2 + 1 and should be counted as one way of amount decompositions.
public static int change(int amount, int[] coins) {
return change(amount, coins, 0, new Integer[amount + 1][coins.length]);
}
public static int change(int amount, int[] coins, int pos, Integer[][] memo) {
if (amount == 0) return 1;
if (amount < 0) return 0;
if (memo[amount][pos] != null) return memo[amount][pos]; // first key
int ret = 0;
for (int i = pos; i < coins.length; i++) {
ret += change(amount - coins[i], coins, i, memo); // second key - "i" without increment
}
memo[amount][pos] = ret;
return ret;
}
}