Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.
这里相同组合，不同顺序被认为是不同的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public int combinationSum4(int[] nums, int target) {
int[] dp = new int[target + 1];
dp[0] = 1;
for(int i = 1; i <= target; i++) {
for(int num: nums) {
if(i - num >= 0) {
dp[i] += dp[i - num];
}
}
}
return dp[target];
}
}
|
这里有顺序，也就是说同一种组合只能有一种顺序，所以外层是coins的循环
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public int change(int amount, int[] coins) {
int[] dp = new int[amount + 1];
dp[0] = 1;
for(int coin: coins) {
for(int i = 1; i <= amount; i++) {
if(i - coin >= 0) {
dp[i] += dp[i - coin];
}
}
}
return dp[amount];
}
}
|
