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]

CodePudding user response：

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)

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))

It is all just Fibonacci sequence, in fact :)

So there is in fact a closed formula.