题目

leetcode:377

代码与解析

献上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]