python 算法 day5

动态规划

动态规划是用来求最优解问题的解决策略之一

一个最典型例子：用最少的硬币找零

比如：一美元购买37美分商品，用来找零的硬币最小数量是多少（一般有1,5,10和25美分的硬币）

首先我们使用最大面值的硬币（25美分），也是尽可能多的使用，接着再使用下一个面值最大的这种方法被称为贪心算法

但如果有21美元时，贪心算法依然会首先选择25美分的，答案也仍然没有变化，而最优解是三个21美分的硬币

我们可以根据递归，首先根据一美分去找，如果价值不匹配，我们就再加上一美分减去1美分找零总数的最小的整数值

一个低效的方法

def reticon(coinValueList , change):
    mincoin = change
    if change in coinValueList:
        return 1
    else:
        for i in [c for c in coinValueList if c<=change]:
            print(i)
            numcoin = 1 + reticon(coinValueList,change-i)
            if numcoin < mincoin:
                mincoin = numcoin
    return mincoin


print(reticon([1,5,10,25],63))

图中每一个点对应一个retcion调用，主要问题我们做了大量重复性计算列如：15美分的找零最优解至少三次1、5、10，每一次计算都需要调用52次函数

减少工作量的关键在于记住一些出现过的结果，这样就能避免重复计算我们已经知道的结果

一个简单的解决方法：

我们将所找到的给硬币找零的最小数目储存在一个表中，然后计算最小值之前，可以先查看表中结果是否已知，如果有了，就可以直接调用，而不是重复计算。

def reticon(coinValueList , change,knowresult):
    mincoin = change
    if change in coinValueList:
        knowresult[change]=1
        print(type(knowresult))
        return 1
    elif knowresult[change]>0:
        return knowresult[change]
    else:
        for i in [c for c in coinValueList if c<=change]:

            numcoin = 1 + reticon(coinValueList,change-i,knowresult)
            if numcoin < mincoin:
                mincoin = numcoin
                knowresult[change] = mincoin
    return mincoin


print(reticon([1,5,10,25],63,[0]*64)）

上述算法只是使用一种叫做“函数值缓存”来改善性能，真正的动态规划会采用更系统的方法去解决问题，把已经知道的最好的路径存起来，下次遇到可以直接用。动态规划的解决方法是从为第一分找零开始的最优解逐步加上去的，直到我们需要的找零数，这就保证了算法在每一步过程中，我们已经知道了兑换更小数值零钱所需硬币数量的最小值。

1	2	3	4	5	6	7	8	9	10
1
1	2
1	2	3
1	2	3	4
1	2	3	4	1

一个新的算法

def dpMake(coinValueList,change,minCoins):
    for cents in range(change+1):
        coinCount = cents
        for j in [c for c in coinValueList if c<=cents]:
            if minCoins[cents-j] + 1 <coinCount:
                coinCount = minCoins[cents-j] + 1
        minCoins[cents] = coinCount
    return minCoins[change]

dpmake有三个参数：一个有效面值的列表我们想要兑换的硬币数值一个包含所有部分找零最优解的列表

当程序运行时 mincoins会包含从0到所需兑换数值中每一个数值对应的最优解。