05 August 2008
共有多少种组合组成target
DP - 类似爬梯子和unique paths总共有多少种做法
Time: O(n * amount), where n is length of coins
Space: O(n * amount)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public int change(int amount, int[] coins) {
int len = coins.length;
int[][] dp = new int[len + 1][amount + 1];
for (int i = 0; i <= len; i++) {
dp[i][0] = 1; // have 1 way to change 0 amount
}
for (int i = 1; i <= len; i++) {
for (int j = 1; j <= amount; j++) {
dp[i][j] = dp[i - 1][j]; // skip ith coin
if (j >= coins[i - 1]) {
dp[i][j] += dp[i][j - coins[i - 1]]; // use ith coin
}
}
}
return dp[len][amount];
}
}
优化空间
Time: O(n * amount), where n is length of coins
Space: O(amount)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public int change(int amount, int[] coins) {
int len = coins.length;
int[][] dp = new int[2][amount + 1]; // 只存两个值
for (int i = 0; i <= len; i++) {
dp[i % 2][0] = 1; // have 1 way to change 0 amount
}
for (int i = 1; i <= len; i++) {
for (int j = 1; j <= amount; j++) {
dp[i % 2][j] = dp[(i - 1) % 2][j]; // skip ith coin
if (j >= coins[i - 1]) {
dp[i % 2][j] += dp[i % 2][j - coins[i - 1]]; // use ith coin
}
}
}
return dp[len % 2][amount];
}
}
top down
Time: O(n * amount), where n is length of coins
Space: O(n * amount)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public int change(int amount, int[] coins) {
Integer[][] dp = new Integer[coins.length][amount + 1];
return dfs(coins, 0, amount, dp);
}
int dfs(int[] coins, int i, int amount, Integer[][] dp) {
if (amount == 0) return 1;
if (i == coins.length) return 0;
if (dp[i][amount] != null) return dp[i][amount];
int ans = dfs(coins, i + 1, amount, dp); // skip ith coin
if (amount >= coins[i])
ans += dfs(coins, i, amount - coins[i], dp); // use ith coin
return dp[i][amount] = ans;
}
}