题目

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]
分类: 算法

0 条评论

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

站点统计

  • 文章总数:304 篇
  • 分类总数:19 个
  • 标签总数:189 个
  • 运行天数:852 天
  • 访问总数:459535 人次
ICP备案号: 辽ICP备20003309号