Some questions

1. Change coints

Problem:

Assume we have $n$ kind of coins as change $\{c_1, c_2, ..., c_n\}$, $m$ is the amount of money needs to change. How many methods are there to change the money?

Example

n = 3, {1, 2, 5}
m = 100



In [10]:

    
# change coins
# TODO: find all the combination instead of just number of combination?
# TODO: find the min number coint used?

def change_coins(coins: list, n: int, m: int):
    """

    :param m: the amount of money
    :param n: the type of coins
    """
    dp = [0 for i in range(m+1)]
    dp[0] = 1  # base case, m = 0, method is 1

    for coin in coins:
        for _ in range(m):
            money = _ + 1
            dp[money] += dp[money-coin]

    return dp[m]
    
# test
coins = [1, 2]
n = 2
m = 4
print(change_coins(coins, n, m))

2. Plant flowers

Problem:

You can painting a fence made of N boards. You have 2 buckets of paint - black and white. Ypu can not paint more than 2 adjacent voards with the same paint. How many ways are there to paint the fence?

Reference: https://codereview.stackexchange.com/questions/63614/count-number-of-ways-to-paint-a-fence-with-n-posts-using-k-colors



In [16]:

    
# Method 1

def count_1(n: int, m: int):
    """
    :param n: the number of boarder
    :param m: the number of colors
    """
    # base case
    if n <= 0:
        return 0
    if n <= 2:
        return m ** n  # 2 x2 for 4

    sum = 0
    sum += (m-1)*count_1(n-2, m)  # Why m-1. Because we have to make sure that the last color is different from the previous one.
    sum += (m-1)*count_1(n-1, m)

    return sum

# test
n, m = 5, 3
print(count_1(n, m))

3. Jumping rabit!

Problems:

THe road map for the rabit is a list with length of $m$, the rabit can either jump 1 step or 2 steps per jump. How many jumping methods are there for the rabit reach the end (never jump back).



In [2]:

    
# 3. Jumping rabit
mem = {}
def jump_rabit(m: int):
    """"""

    if m <= 3:
        return m-1

    if m in mem.keys():
        return mem[m]
    else:
        mem[m] = jump_rabit(m-1) + jump_rabit(m-2)

    return mem[m]

# test
m = 3
print(jump_rabit(m))



In [ ]: