题目链接
思路
分析动态规划题目的时候只需要考虑最后一个阶段，因为所有的阶段转化都是相同的，考虑最后一个阶段容易发现规律
在数组的动态规划问题中，一般 dp[i] 都是表示以 nums[i] 为结尾的状态；dp[i][j] 分别表示 以 nums1[i] 和 nums2[j] 为结尾的状态，以此类推
字符串也是个数组，是字符数组
表示状态
这个题非常类似于爬楼梯问题：楼梯的阶数一共为target，一次可以走的步数为nums[i]。 一共有多少种走法？
如果这么考虑的话，其实和【DP】LeetCode 70. 爬楼梯非常相似，只不过在70题中固定为 nums = [1, 2]。
所以我们用 dp[i] 表示在达到数值为 i 时（即上到第 i 层台阶时）能凑出的排列个数（即上楼梯的方法数）
注意：题目虽然叫做《组合总和》，但是因为“顺序不同的序列被视作不同的组合”，所以其实是种排列
找状态转移方程
在70题中我们的状态转移方程如下：
\[dp[i] = dp[i - 1] + dp[i - 2] \]这个公式还可以这么写：
\[dp[i] = \sum^{n - 1}_{j = 0}{dp[i - nums[j]]}, i \geq nums[j] \]这样的话就推广到了普遍的 nums 数组情况
边界处理
dp[0][0] = 1
代码
dp数组版
class Solution {
public int combinationSum4(int[] nums, int target) {
// 爬楼梯问题
// 楼梯的阶数一共为target,一次可以走的步数为nums[i]。求一共有多少种走法
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]){
dp[i] += dp[i - nums[j]];
}
}
}
return dp[target];
}
}