初识动态规划

在将动态规划之前，我们来继续深入了解以下递归，这样有利于我们对动态规划的了解，
我们还是以斐波那契数列为例，这里我们已经写下了如下的代码：

defx(n):if n==0:return0elif n==1:return1else:return x(n-1)+ x(n-2)

但是我们会发现每个问题被我们分解成为了两个问题，但是我们想一想？这时候时间复杂度不就变成了2**n,这会导致计算十分费时间，我们可以尝试以下计算第50个数，会发现它会计算很长时间，有可能还没有计算出来，这时候我们就可以进行优化。
我们思考一下，我们在计算中会计算很多重复的数，x(n-2)就会计算两次，后面的计算次数是不是会更多？我们可以用字典将每个数据进行储存，储存完成减少了重复计算了

memo={}deffib1(n):if nin memo:return memo[n]else:if n<=2:
            f=1else:
            f= fib1(n-1)+ fib1(n-2)
        memo[n]= freturn f

我们这时候就利用了字典提高了递归效率，时间复杂度只有n，但是我们这是自上向低的计算，我们可以换一种计算方式，让他实现自底向上的计算：

deffib2(n):
    fib={}for kinrange(n+1):if k<=2:
            f=1else:
            f= fib[k-1]+ fib[k-2]
        fib[k]= freturn fib[n]

这里发现我们根本没有用到了递归，这里时间复杂度也是n。
动态规划，就是以这种方式，找到了类似f = fib[k-1] + fib[k-2]这种等式(表达式)，然后进行我们的计算，这里就需要我们分析问题找到表达式了。

细致讲解

很多计算机被用于优化某些值，如两点之间找到最短路径，计算机科学家采用很多策略来解决这些问题，动态规划就是策略的其中之一。
我们以一道经典的例题来讲解以下动态规划。
在找零的时候使用最少的硬币。假设莫格自动售货机制造商希望每笔交易中给出最少的硬币，一个顾客在使用一美元的纸币购买了价值37美分的物品，最少该找多少硬币呐?答案是六枚，25美分的两枚，10美分的一枚，1美分的3枚。
如何计算呐？从面值最大25美分开始，使用尽可能多的硬币，然后尽可能使用第二大的硬币，这种方法叫做贪婪算法，试图最大程度的解决问题。
我们尝试一种更优的解法我们来先看一下递归解法，首先确定基本情况，如果要找的零钱金额与硬币的面值相同，那么只需要找1枚硬币即可。
如果要找的零钱的金额与硬币面值不相同，则有多种选择，一枚一分的硬币加上找零金额减去1之后所需的金额，一枚五分的硬币…等等
我们出示以下代码：

defrecMC(coinValueList, change):
    minCoins= changeif changein coinValueList:return1else:for iin[cfor cin coinValueListif c<= change]:
            numCoins=1+recMC(coinValueList, change-i)if numCoins< minCoins:
                minCoins= numCoinsreturn minCoins

但是他的效率十分低，我们针对63分的情况，要计算67716925次递归才能完成。其中主要因为我们将大量时间和资源浪费到了重复计算中了

如果我们可以用查询表后，似乎可以减少一点计算量。

defrecDC(coinValueList,change, knowResults):
    minCoins= changeif changein coinValueList:
        knowResults[change]=1return1elif knowResults[change]>0:return knowResults[change]else:for iin[cfor cin coinValueListif c<= change]:
            numCoins=1+recMC(coinValueList, change-i, knowResults)if numCoins< minCoins:
                minCoins= numCoins
                knowResults[change]= minCoinsreturn minCoins

这里我们把递归调用降低到了221次，但是我们发现它并不是太正规，如果查看knowResults表，会发现其中有一些空白的地方，我们做的优化并不是动态规划，而是通过记忆(或者叫缓存)的方法来优化程序新跟那个，但是仍然需要计算221次，
我们来尝试用动态规划进行解决我们来看找零11分硬币，我们从一分开始计算

上面的图片为我们进行了展示，11分的情情况如下图

我们有三个可选方案。
1.一枚一分的加上十分的零钱最少需要的硬币（11-1）
2.一枚五分的硬币加上六分零钱最少需要的硬币（11-5）
3.一枚十分的加上找一分零钱最少需要的硬币（11-10）
这里第一个和第三个均为最优解，即需要两枚硬币。
函数如下

#动态规划解法，函数接受三个值，硬币面值列表，找零金额，以及由每个找零金额所需要的最少硬币数构成的列表,自底向下的计算defdpMakeChange(coinValueList, change, minCoins):for centsinrange(change+1):
        coinCount= centsfor jin[cfor cin coinValueListif c<= cents]:if minCoins[cents-j]+1< coinCount:
                coinCount= minCoins[cents-j]-1
        minCoins[cents]= coinCountreturn minCoins[change]#dp是动态规划的简写

我们从第四行开始的循环针对有cents指定的找零金额考虑所有可用的面值，我们采用自底向上的方法进行计算。
尽管找零算法再寻找最少硬币数时表现出色，但是没有记录所以用硬币，所以并不能解决我们的实际问题，我们可以尝试通过记录minCoins表中每一项
所加的硬币，可以轻松拓展函数，并通过它知晓之前所加的硬币。
代码如下：

defdpMakeChange(coinValueList, change, minCoins,coinsUsed):for centsinrange(change+1):
        coinCount= cents
        newCoin=1for jin[cfor cin coinValueListif c<= cents]:if minCoins[cents-j]+1< coinCount:
                coinCount= minCoins[cents-j]-1
                newCoin= j
        minCoins[cents]= coinCount
        coinsUsed[cents]= newCoinreturn minCoins[change]defprintCoins(coinsUsed, change):
    coin= changewhile coin>0:
        thisCoin= coinsUsed[coin]print(thisCoin)
        coin-= thisCoin

这里所有问题我们都已经解决完成了。我们可以进行一下简单的实践，

应用实践

https://leetcode-cn.com/problems/find-the-minimum-number-of-fibonacci-numbers-whose-sum-is-k/