硬币问题(凑零钱) 动态规划

infinity = 9999
def coin_change(coins, a):
    dp = []
    '''初始化过程'''
    dp.append(0)
    min_amount = min(coins)
    for i in range(1, min_amount):
        dp.append(infinity);
    
    '''动态规划自底向上方法计算过程'''
    for i in range(min_amount, a + 1):
        min_count = infinity
        for c_j in coins:
            if i >= c_j and dp[i - c_j] + 1 < min_count:
                min_count = dp[i - c_j] + 1
        dp.append(min_count)
    return dp[a]

时间复杂度分析:求最小硬币面值(\(O(n)\))和初始化dp数组( \( O(1) \) )可以忽略不计,动态规划过程中有两层循环,外层最多执行a次,内层最多执行n次,因此该算法最坏的时间复杂度的 \( O(an) \)

空间复杂度分析 :dp数组所占用的空间为 \(O(a) \)

发表评论

电子邮件地址不会被公开。 必填项已用*标注