这个题的思路是动态规划，DP[n]代表能组成n的组合数。算1-n就可以，因为都是正数。
算dp[n]的时候遍历num[1] to num[n] index = i
如果i < dp[n] 那么dp[n] = dp[n] + dp[n-i]
从逻辑上来考虑比较复杂，比如4=0+4 1+3 2+2 3+1 4+0
0+4 1 （1+1+1+1）
1+3 1的组合3的组合
2+2 2的组合2的组合
3+1 3的组合*1的组合
4+0 1 （4）
1+4+4+4+1 然后除以2 因为重复了一遍
但是结果似乎不对
看答案 算法是
dp[n] = dp[n] + dp[n-i]
比如4
从1遍历到4
1<4
dp[4] = dp[4] + dp[4-1]
public int combinationSum4(int[] nums, int target) {
int[] dp = new int[target+1];
dp[0] = 1;
for(int n = 1; n < target+1;n++)
{
for(int m = 0; m < nums.length;m++)
{
if(n >= nums[m]) dp[n] = dp[n] + dp[n-nums[m]];
}
}
return dp[target];
}
代码很简单，但是发现这种逻辑很难，比如我就觉得无从下手。。
感觉DP的题重点是找到动态规划的递推式，已经习惯于DP[N]从dp[n-1]来找
这个题就不是。。
递推式dp[n] = dp[n] + dp[n-i]
二刷：
一开始先排序，然后因为1，3和3,1这种都算有效，所以滑动窗口之类的没有意义。
而且，还有错，不能有效break。
看一刷的答案，发现是动态规划。
当时不理解，现在理解了。
public int combinationSum4(int[] nums, int target)
{
Arrays.sort(nums);
int[] dp = new int[target+1];
dp[0] = 1;
for(int i = 1; i <=target;i++)
{
for(int j = 0; j < nums.length; j++)
{
if(i - nums[j]>=0) dp[i] = dp[i] + dp[i - nums[j]];
else break;
}
}
return dp[target];
}
然后改进了一下，先排序，可以有效break，比直接遍历快一点点，而且好理解。
理解容易，不一定能想出来。
一开始有那个点意思，想到的是方法是递归。比如(nums[],target = 4
递归就变成(nums[],target-nums[n])
仔细想想应该就是动态规划的思路，然后通过DP来减少重复计算。
DP的双For loop大概可以总结为 i = 1 ~ n; j = 0 ~ i,从左边开始的话。
右边开始是 i = n~0; j = n~n-i???
三刷。
照着刚才的惯性DFS结果TLE了，做的时候就觉得不对……
应该是DP。。
dp[i]代表:
和是i的组合有多少种 的dp[4] = 1 + dp[3]
4 = 1 + 3
4 = 2 + 2
4 = 3 + 1
A + B的时候前面的A是nums里的数， 后者是可以组成B的左右组合，不能是dp[1] + dp[3]这样的话就重复计算了.
dp[1] + dp[2] 和 dp[2] + dp[1]计算了2次1+1+1...，这就是为啥一刷的办法不对。
Time: O(nk)
Space: O(k)
public class Solution {
public int combinationSum4(int[] nums, int target) {
if (nums.length == 0) return 0;
Arrays.sort(nums);
int[] dp = new int[target+1];
dp[0] = 1;
for (int i = 1; i <= target; i++) {
for (int j = 0; j < nums.length; j++) {
if (i - nums[j] >= 0) dp[i] += dp[i - nums[j]];
else break;
}
}
return dp[target];
}
}