CODEWITHSUNDEEP
pythonpython-3.x
Singham
Singham

Reputation: 313

What I am doing wrong here - dynamic problem

PROBLEM STATEMENT:

You are about to go shopping for some candy in a local store. They sell candy for either $1 or $2 pieces. You would like to know in how many unique ways you can purchase candy based on the amount of money you have.

def buying_candy(amount_of_money):

    if amount_of_money < 2:
        return 1

    dp = {0: 1, 1: 1}
    x = 1
    while x < amount_of_money:
        if x not in dp:
            dp[x] = 1
        dp[x] = dp[x] + dp[x - 1]

        x += 1

    return dp[amount_of_money - 1]

print(buying_candy(4))

OUTPUT: 5

EXPLANATION:

1 + 1 + 1 + 1
2 + 2
2 + 1 + 1
1 + 2 + 1
1 + 1 + 2

UPDATE:

SOLUTION of Problem

def buying_candy(amount_of_money):

    if amount_of_money < 2:
        return 1
    
    dp = {
        0: 1,
        1: 1
    }
    x = 2
    while x < amount_of_money + 1:
        if x not in dp:
            dp[x] = 1
        dp[x] = dp[x - 1] + dp[x - 2]

        x += 1
    
    return dp[amount_of_money]

Upvotes: 0

Views: 668

Answers (1)

Orius
Orius

Reputation: 1093

  1. This problem does not require dynamic programming. Denote the amount of money by n. There are between 0 and ⌊n/2⌋ twos. If the number of twos is k, then the number of ones is n−2k, and the total number of ones and twos is n-2k+k = n-k. Each solution with k twos corresponds to choosing k out of the n-k positions for the twos. So the total number of solutions with k twos is (n-k choose k), and the total number of solutions is the sum of this expression over k from 0 and ⌊n/2⌋.

    In Python:

    import math
n = 4 # amount of money
total = sum(math.comb(n-k,k) for k in range(n//2+1)) # total number of solutions
print(total)

  2. If the rules of the game require using dynamic programming, here is a correct version:

    def buying_candies(n):
    if n < 2:
        return 1
    dp = [1, 1] # use list instead of dictionary, as keys are 0,1,2,...
    for i in range(2, n+1):
        dp.append(dp[i-1] + dp[i-2])
    return dp[n]

print(buying_candies(4))

  3. It is all just Fibonacci sequence, in fact :)

    So there is in fact a closed formula.

Upvotes: 1

Related Questions