题目
代码与解析
献上carl大佬的解析
献上leecode平台解析
动归五部曲:
- 确定dp数组及下标的含义
dp[i]凑成目标正整数为i(0-target)的排列个数 -
确定递推公式
-
初始化dp数组
一定要初始化dp,不然得到的dp就是一堆0,[0,0,0,0]
- 确定遍历顺序
题目中说,个数可以无限适用,是完全背包问题
> 求组合数就是外层for循环遍历物品,内层for遍历背包。
> 求排列数就是外层for遍历背包,内层for循环遍历物品。
这里很巧,只是一个顺序的问题,外层是物品的话只能{1,2}, {1,3},{1,4},不会出现反顺序
- 推导dp
func combinationSum4(nums []int, target int) int {
// arr := []int{}
dp := make([]int, target+1)
dp[0] = 1
for j:=0;j<=target;j++ {
for i:=0 ;i < len(nums);i++ {
if j >= nums[i] {
dp[j] += dp[j-nums[i]]
}
}
}
// fmt.Println(dp)
return dp[target]
}
或者
func combinationSum4(nums []int, target int) int {
dp := make([]int, target+1)
dp[0] = 1
for j:=0;j<=target;j++ {
for _, i:=range nums {
if j >= i {
dp[j] += dp[j-i]
}
}
}
// fmt.Println(dp)
return dp[target]
}
python
版
def combinationSum4(self, nums, target):
dp = [0] * (target + 1)
dp[0] = 1
for i in range(1, target+1):
for j in nums:
if i >= j:
dp[i] += dp[i - j]
return dp[-1]