专栏首页Bingo的深度学习杂货店【DP】377. Combination Sum IV

【DP】377. Combination Sum IV

问题描述:

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Example:
nums = [1, 2, 3]
target = 4

The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

Note that different sequences are counted as different combinations.

Therefore the output is 7.

Follow up:
  • What if negative numbers are allowed in the given array?
  • How does it change the problem?
  • What limitation we need to add to the question to allow negative numbers?

解题思路:

方法1:BFS(超时 TLE)

第一种想法是使用 【DP、BFS】322. Coin Change 这道题中的 BFS 方法,只不过这时 BFS 的目标是求能到达 amount 的次数,并且不使用 visited 剪枝。因此,很快拍出下面代码:

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        dis = [(0, 0)]
        layer = 0
        ans = 0
        while len(dis) > 0:
            while len(dis) > 0 and dis[0][1] == layer:
                tem = dis.pop(0)
                if tem[0] == target:
                    ans += 1
                for num in nums:
                    if tem[0] + num <= target:
                        dis.append((tem[0]+num, layer+1))
            layer += 1
        return ans

但是这种情况下,超时了。假设硬币中有 1,amount 又很大,构造这棵树的时间复杂度最坏可能达到 O(2^(amount)),这是不可接受的,因此这种想法不行。

方法2:DP(接受 AC)

如果使用动态规划的思想,就和 Leetcode 【DP】518. Coin Change 2 的解法很类似了,只不过这道题是求排列数,找硬币的题是求组合数。

在找硬币问题中分析了,由于是求组合数,所以外层循环应该是对 coins 的循环。但是这道题是是求排列数,nums 里面的数可以不同顺序的出现,因此这道题的内层循环应该是 nums,外层循环应该是不同的目标 i。

因此,类似于 【DP】518. Coin Change 2 ,可以想到如下算法:

  • 创建一个 dp[1+target] 数组,其中 dp[i] 表示目标为 i 时的排列方案数;
  • 初始化 dp[0] = 1,表示目标为 0 的时候方案数为 1,其他位置 dp[i] 为 0;
  • 外层循环是对不同目标 i 的循环,内层循环是对 nums 的循环;可以想到转移方程:dp[i] = ∑ dp[i-nums[j]],表示:目标为 i 时的方案数 = 目标为 i-nums[j] 的方案数的加和。∑ 次数等于内层循环次数。
  • 最后,dp[-1] 就是答案。
Python3 实现:
class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        dp = [1] + [0] * target
        for i in range(1, target+1):
            for num in nums:
                if i >= num:
                    dp[i] += dp[i-num]
        return dp[-1]

print(Solution().combinationSum4([2,1], 3))  # 3 (111、12、21)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Leetcode【120、611、813、915】

    容易想到用动态规划求解,dp[i][j] 存储累加到位置 (i, j) 的最小路径和。

    echobingo
  • 【DP】64. Minimum Path Sum

    Given a m x n grid filled with non-negative numbers, find a path from top left t...

    echobingo
  • Leetcode【712、746、877】

    读完题目后发现:把两个字符串中多余的字符删除后,最后留下的字符串是两个字符串的最长公共子序列。因此这道题可以像最长公共子序列一样,采用动态规划的思想解决:常考的...

    echobingo
  • LeetCode 1546. Maximum Number of Non-Overlapping Subarrays With Sum Equals Target(动态规划)

    题解:动态规划 dp[i]表示从0到i的子数组的答案。维护前缀数组sums[],我们维护一个记录前缀和的map,map[x]表示前缀和是x距离当前i最近的下标。

    ShenduCC
  • Dynamic Programming - 377. Combination Sum IV

    Given an integer array with all positive numbers and no duplicates, find the num...

    用户5705150
  • 大话 Select、Poll、Epoll

    提到select、poll、epoll相信大家都耳熟能详了,三个都是IO多路复用的机制,可以监视多个描述符的读/写等事件。

    黄日成
  • python中装饰器的原理

    装饰器这玩意挺有用,当时感觉各种绕,现在终于绕明白了,俺滴个大爷,还是要慢慢思考才能买明白各种的真谛,没事就来绕一绕

    py3study
  • 为PHP站点开启自定义Apache服务器模块

    为了满足你对PHP应用程序的所有要求,有时你需要添加自定义模块。模块化架构是Apache服务器全球普及的主要原因之一。大多数网站都是通过这个服务器搭建的,我们的...

    Techeek
  • 为PHP站点启用自定义Apache服务器模块

    为了满足您的PHP应用程序的所有要求,有时您需要添加自定义模块。模块化架构是Apache服务器遍及全球的主要原因之一。大多数网站架设在Apache服务器上,我们...

    QonkeyQun
  • 为PHP站点启用自定义Apache服务器模块

    为了满足您的PHP应用程序的所有要求,有时您需要添加自定义模块。模块化架构是Apache服务器遍及全球的主要原因之一。大多数网站架设在Apache服务器上,我们...

    QonkeyQun

扫码关注云+社区

领取腾讯云代金券