组合总和IV(力扣---动态规划)
文章目录
- 1.题目描述
- 2.解题思路
- 3.代码实现
1.题目描述
题目描述见：组合总和IV
2.解题思路
视频参考： 组合总和IV
以上述的示例1为例：
dp[4]的含义是什么？和为4的组合有多少种
一般动态规划是可以由前面的dp[3]推导而来的
dp[3] 有 [ [1,1,1], [1, 2], [2,1], [3] ]这些方法
那么如果nums数组种含有元素1，则有 [ [1,1,1]+1, [1, 2]+1, [2,1]+1, [3]+1 ]
dp[4] = dp[3]
但是dp[4]不仅仅只有dp[3]得到的。也可能是dp[2],dp[1],dp[0]
我们再举一个例子dp[2] 有[[1,1],[2]]如果nums数组种有2那么就一定可以凑成dp[4]
因为[[1,1]+2,[2]+2]
所以可以归纳出dp[4]=dp[3]+dp[2]+dp[1]+dp[0]
dp[0]=1
dp[1] = 是否存在dp[0] + 1 存在dp[1] = 1
dp[2] = 是否存在dp[1]+1,dp[0]+2 都存在 ，则dp[2]=2
3.代码实现
dp = [0] * (target+1)
dp[0] = 1
for j in range(1, target+1):for i in range(len(nums)):if j-nums[i] >= 0: dp[j] += dp[j-nums[i]]return dp[-1]