动态规划- python及递归

• 零钱兑换问题---动态规划解法
• • 采用动态规划来解决11分钱的兑换问题
  • 动态规划扩展算法
  • LeetCode 322. 零钱兑换

递归算法https://blog.csdn.net/suwuzs/article/details/121666346
在递归优化的过程中，我们用了中间结果记录的方法。这种方法叫做memoization（记忆化/函数值缓存）技术，可以提高递归解法的性能。

• 零钱兑换的动态规划算法是从最简单的‘1分钱’找零的最优解开始，逐步递加上去，直到我们需要的找零钱数；
• 在找零递加的过程中，设法保持每一分钱的递加都是最优解，一直加到求解找零钱数，自然得到最优解。

递加的过程能保持最优解的关键是，依赖于更少钱数最优解的简单计算，而更少钱数的最优解已经得到了了。

问题最优解包含了更小规模子问题的最优解，这是一个最优化问题能够用动态规划策略解决的必要条件。

numCoins = min(
    1 + numCoins(original - 1),
    1 + numCoins(original - 5),
    1 + numCoins(original - 10),
    1 + numCoins(original - 25),
)

从1分钱开始兑换，逐步建立一个兑换表；

计算11分钱的兑换法，我们氛围以下几步：

• 首先减去1分钱，剩下10分钱，查表最优解是1；（1+1）
• 然后减去5分钱，剩下6分钱，查表最优解是2；（1+2）
• 最后减去10分钱，剩下1分钱，查表最优解是1。（1+1）

通过上述过程，得到的最小值，最优解是2。

def dp_change(coinList, change, minCoins):
    for cent in range(1,change+1):
        coinCount = cent
        for i in [c for c in coinList if c <= cent]:
            if minCoins[cent-i] + 1 < coinCount:
                coinCount = minCoins[cent - i] + 1
        minCoins[cent] = coinCount

    return minCoins[change]
ls = [1,5,10,21,25]
print(dp_change(ls,63,[0]*64))

• 动态规划算法并不是递归函数；
• 动态规划的主要思想；
  从最简单情况开始到达所需找零的循环，其每一步都依靠以前的最优解来得到本步骤的最优解，直到得到答案。

返回硬币的组合；

只需要在生成最优解列表同时跟踪记录所选择的那个硬币币值即可。

在得到最后的解后，减去选择的硬币币值，回溯到表格之前的部分找零，就能逐步得到每一步所选择的硬币币值。

def dp_change(coinList, change, minCoins, coinUsed):
    for cent in range(1,change+1):
        coinCount = cent
        newCoin = 1 #初始化新加硬币
        for i in [c for c in coinList if c <= cent]:
            if minCoins[cent-i] + 1 < coinCount:
                coinCount = minCoins[cent - i] + 1
                newCoin = i #对应最小数量，所减的硬币
        minCoins[cent] = coinCount
        coinUsed[cent] = newCoin #记录本次步骤所加的1个硬币
    return minCoins[change]
    
def printCoins(coinUsed,change):
    coin = change
    while coin > 0:
        thisCoin = coinUsed[coin]
        print(thisCoin)
        coin = coin - thisCoin
ls = [1,5,10,21,25]
amt = 63
coinUsed = [0]*(amt+1)
print(dp_change(ls,amt,[0]*(amt+1),coinUsed))
print('-------')
printCoins(coinUsed,amt)

输出：
3
-------
21
21
21

def dp_change(coinList, change):
    minCoins = [float('inf')] * (change+1)
    minCoins[0] = 0
    for coin in coinList:
        for x in range(coin, change+1):
            minCoins[x] = min(minCoins[x], minCoins[x-coin] + 1)
        
    return minCoins[change] if minCoins[change] != float('inf') else -1

ls = [1, 5, 10, 21, 25]
print(dp_change(ls, 63))