Python DP ~quadratic, simple explanation & 10 line solution


  • 0
    E

    The idea

    Let w(n) be the number of ways to make n using a set of number nums.

    • The number of ways to make n is the sum of the number of ways to make n ending with i for every i in nums.
    • The number of ways to make n ending with i is w(n-i): just sum up to n-i then add i.

    In short, this sums up (pun intended) to:

    w(n) = sum of w(n-i) for i in nums

    The code

    In Python, this translates to:

    def combinationSum4(nums, target):
        n, dp = 1, [1]
        nums.sort()
        while n <= target:
            ans = 0
            for i in nums:
                if i > n: break
                ans += dp[n - i]
            dp.append(ans)
            n += 1
                
        return dp[target]
    

    Let n = target and m = len(nums)
    The complexity is O(n*min(n,m) + mlog(m)). At the time of writing, this solution beated 100% with 39ms. I believe this optimal.

    Bonus

    As a side note, if nums = {1, 2, ..., n-1} then w(n) = 2^(n-1)-1, which is the (n-1)th Mercenne number.

    In python this would look like this:

    def combinaisonsTo(target):  # if nums = [1, ... target-1]
        return (1 << target - 1) - 1
    

    EDIT: Math $$nope$$ did not work although it is said that it does, I will update this to real maths if leetcode answers my bug report !


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.