动态规划算法
动态规划算法通常用于求解具有某种最优性质的问题。动态规划算法与分治法类似，其基本思想都是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到的子问题往往不是互相独立的。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。用一个表（备用表）来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。
问题描述：
现存在若干面值为1,5,11,20,50面值的硬币，问兑换总值为N面值有多少换钱方法？
解决这个问题其实也可以考虑使用贪心算法，每次使用面值最大的硬币，不足部分再用小额硬币补充。但是，使用贪心算法只能保证每一步取的是局部最优解，并不能保证最终结果是全局最优解。以兑换15元为例，贪心算法给出的组合方案为{11,1,1,1,1}，但其实最优方案为{5,5,5}。使用动态规划算法就能避免该问题。因为动态规划可以保证每次取到的子问题的解是最优解。
动态规划解题思路
测试样例：
n=3,aim=,penny【2,1,4】
返回值为：
9
解析
将找钱的任务划分成如下的小任务。以3种货币种类举例。
大致的想法就是我就用一种货币去凑0-aim的面值。看看当使用一种货币的时候，从0-aim这些面值中每种面值的零钱换钱方法有多少种。之后，我在第一种货币的基础上增加第二种货币，这时候问题就变为使用两种货币的时候，从0-aim这些面值中每种面值的的零钱换钱方法有多少种。在这个时候我们会发现，对于一个面值而言，它的换钱的方法是包括两方面。一方面是使用一种货币的进行兑换的方法数量。另一种就是使用两种货币兑换的方法数量。以此类推，当我们加入第三个货币的时候，此时兑换的方法是由使用两种货币兑换的方法数量和使用三种货币兑换的方法数量组成的。这样我们就会将一个面值的兑换问题大体上建立一个概念，接下来就是具体分析如何实现了。
我们先建立一个数组dp[n][m]，n就是货币的种类数量，m就是aim+1。dp[n][m]用来表示使用前n种货币兑换m面值的种数。根据我们前面的分析。会出现以下两种状况。
第一种就是使用第n种货币：dp[n][m] = dp[n-1][m]+dp[n][m-peney[n]]。
这里面dp[n-1][m]为兑换m面值使用n-1种货币时的兑换方法数量。dp[n][m-peney[n]]为兑换m-peney[n]面值使用n种货币时的兑换方法。
第二种就是无法使用第n种货币(货币的面额比需要兑换的m值要大)：dp[n][m] = dp[n-1][m] 这个时候使用n种货币去兑换面值零钱的方法种数和适用n-1种货币去兑换m面值零钱的方法总数是一样的。
实例讲解
下面我们就以面值为【2,1,4】 aim=9的情况通过excel具体表现一下填表的过程。
第一步.通俗点就是把二维数组的边界值都填好。第一行很好理解就是，我只用面值2的货币去凑9。结果就是凑面值0只有一种方法就是一张不拿。凑2就是拿一张，也是一种方法。凑4就是拿两张，依旧只有一种方法。类推凑8就只有拿4张面值2的这一种方法。第一列也好理解，凑0之后啥也不拿这一种方法。
第二步. 这时候我们就要填第二行了，也就是使用两种货币去凑钱这行。那绿框里的一是怎么来的呢。首先我们可以知道待凑的面值1大于等于货币的面值。因此这时候我们是可以使用第三种货币的。根据上面的等式dp[n][m] = dp[n-1][m]+dp[n][m-peney[n]]，我们可以计算出绿框中的数值为1。也就是下图中两个红框内数值的和。
第三步以此类推，使用两种货币这一行也被我们填满了。
第四步.就是填第三行了。这是货币的面值是4，已经比一些要凑的面值都要大了。此时我们会遇到无法使用第四种面值的情况。这时dp[n][m] = dp[n-1][m]。因此此时紫色框内的数值与上一行是一样的。
第五步，就是当待凑面值大于等于货币面值的时候。此时的等式关系又变为dp[n][m] = dp[n-1][m]+dp[n][m-peney[n]]。此时整个数组的值就填完了。右下角的值就是使用3种货币去凑9块钱的时候有多少种方法。
代码实现
class Solution:
def countWays(self,moneys,target):
if len(moneys) == 0 or target < 0:
return 0
dp = [[0 for _ in range(target+1)] for _ in range(len(moneys))]
for i in range(len(moneys)):
dp[i][0] = 1
i = 1
while moneys[0]*i <= target:
dp[0][moneys[0]*i] = 1
i = i + 1
for i in range(1,len(moneys)):
for j in range(1,target+1):
if j >= moneys[i]:
dp[i][j] = dp[i-1][j] + dp[i][j-moneys[i]]
else:
dp[i][j] = dp[i-1][j]
return dp[len(moneys)-1][j]
京公网安备 11010502036488号