# 动态规划问题
# 1. 斐波那契数列
# 2. 凑零钱

# --1-- 斐波那契数列，不是标准动态规划类问题，但是DP数组的使用思想是一样的

def _fib1(n):
    if n == 0:
        return 0
    if n == 1 or n == 2:
        return 1
    return _fib1(n-1) + _fib1(n-2)

def _fib_inter(n):
    a, b = 1, 1
    for _ in range(n-1):
        a, b = b, a + b
    return a

def fib_db(n):
    if n == 1 or n == 2:
        return 1
    if n == 0:
        return 0
    dp = [0]*(n+1)
    dp[1] = dp[2] = 1
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]


# --2-- 凑零钱，给定n种不同币值的银币，面额是c1...cn, 总金额amount，问最少可以使用几个硬币

# 递归解法
def coin_change_recur(coins, amount):
    record = {}
    def recur(n):
        if n in record:
            return record[n]
        if n < 0:
            return -1
        if n == 0:
            return 0
        res = float('inf')
        for coin in coins:
            subproblem = recur(n - coin)
            if subproblem == -1:
                continue
            res = min(res, 1 + subproblem)
        record[n] = res if res > -1 else -1
        return record[n]

    return recur(amount)

# dp解法
def coin_change_dp(coins, amount):
    # 创建一个数组 dp，dp[i] 表示组成金额 i 所需的最少硬币数
    # 初始化 dp 数组，设置一个较大的值代表无法构成金额
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0  # 组成金额 0 不需要硬币，硬币数为 0

    # 遍历每个硬币
    for coin in coins:
        for i in range(1, amount + 1):
            dp[i] = min(dp[i], dp[i - coin] + 1)

    # 如果 dp[amount] 仍然是 inf，说明无法组成该金额，返回 -1
    return dp[amount] if dp[amount] != float('inf') else -1