(动态规划 leetcode377)组合求和IV

确立状态转移方程需要深入理解问题，合理定义子问题，找到边界条件(比如dp[0])，分析状态之间的转移关系（dp和dp之间的关系），并进行验证。

递归是自顶向下，而dp是自下而上

这里是i作为目标值，dp[i]是值在目标值为i的nums的组合数

if(x<=i)//x可以作为组合的数

dp[i]+=dp[i-x];

比如nums={1,3,2}

target=4

i--4的目标值

当目标值为4

dp[4]=dp[3]+dp[1]+dp[2]

4-1=3（dp【3】）

4-1=3（dp【1】）

4-2=2（dp【2】）

class Solution {
public:int combinationSum4(vector<int>& nums, int target) {vector<unsigned>dp(target+1,0);dp[0]=1;//目标值为0，有一个组合就是不选for(int i=1;i<=target;i++)for(auto x:nums){if(x<=i)//当x小于等于目标值的时候可以进行组合dp[i]+=dp[i-x];}return dp[target];// 使用 unsigned 可以让溢出不报错// 对于溢出的数据，不会影响答案的正确性（题目保证）}
};