案例一：有数组penny，penny中所有的值都为正数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个整数aim(小于等于1000)代表要找的钱数，求换钱有多少种方法。

给定数组penny及它的大小(小于等于50)，同时给定一个整数aim，请返回有多少种方法可以凑成aim。
测试样例：
[1,2,4],3,3
返回：2

思路：
1.暴力搜索法：
用零张1元，让[2,4]组成剩下的3，最终方法记为------------res1
用一张1元，让[2,4]组成剩下的2，最终方法数目记为---------res2
用两张1元，让[2,4]组成剩下的1，最终方法数目记为---------res3
用三张1元，让[2,4]组成剩下的1，最终方法数目记为---------res4
最后方法总数为：res1+res2+res3+res4

code

# -*- coding:utf-8 -*-

class Exchange:
    def countWays(self, penny, n, aim):
        # write code here
        return self.process(penny,0,aim)
    def process(self,penny,index,aim):
        res = 0
        # 当索引到达列表终点，判断aim是否为零
        if index == len(penny):  # 注意条件为整个列表的长度
            if aim==0:
                return 1
            else:
                return 0
       # 当索引没有到达列表终点时，需要继续向下计算
        else:
                i = 0
                while penny[index]*i <= aim:
                    res += self.process(penny,index+1,aim-penny[index]*i) 
                    i+=1
        return res

暴力搜索的缺点：会进行相当多重复的计算，
重复计算一个状态举例：
用两张一元，零张两元后，1，[4]
用零张一元和一张两元后，1，[4]
状态发生重复，但是我们仍会计算两次。

记忆搜索法：

我们可以试把已经计算了的值加入到哈希表中，在每次计算前在表中进行查询，如果表中存在则直接使用，不存在则需要暴力计算，计算完成后，再将所得到的值以及对应的状态放入到hash表中。

class Exchange:
    def countWays(self, penny, n, aim):
        # write code here
        dic = [[0 for clo in range(aim+1)]for row in range(n+1)]
        return self.process(penny,0,aim,dic)
    def process(self,penny,index,aim,dic):
        res = 0
        if index == len(penny):
            if aim==0:
                return 1
            else:
                return 0
        else:
            if dic[index][aim]!=0:
                if dic[index][aim]==-1:
                    return 0
                else:
                    return dic[index][aim]
            else:
                i = 0
                while penny[index]*i <= aim:
                    res += self.process(penny,index+1,aim-penny[index]*i,dic) 
                    i+=1
        if res==0:
            dic[index][aim]=-1
        else:
            dic[index][aim]=res
        return res

tips：我们用初始化为零的二维列表来代替没有计算过的状态，用-1来代替计算过但是数值为零的状态。注意初始化二维列表的方法：

a = [[0]*4]*3
print(a)
a[0][0]=1
print(a)

D:\Anaconda3\envs\pytorch\python.exe C:/Users/xiong/Desktop/jobshop.py
[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
[[1, 0, 0, 0], [1, 0, 0, 0], [1, 0, 0, 0]]

动态规划法

1.记忆搜索方法就是某种形态的动态规划算法。
2.记忆搜索方法不关心到达某一个递归过程的路径，只是单纯的对计算递归过程进行记录，避免重复的递归过程。
3.动态规划的方法则是规定好每一个递归过程的计算顺序，一次惊醒计算，后面的计算过程严格依赖前面的计算。
4.两者都是空间换时间的方法，也都有枚举的过程

思路，我们需要从记忆搜索方法中找到某种可以不使用递归的方法，通过恰当的状态设置可以按顺序将所有的值写出来，动态规划就是有顺序的记忆搜索法

class Exchange:
    def countWays(self, penny, n, aim):
        # write code here
        dp = [[0 for clo in range(aim+1)] for row in range(n)]
        for j in range(aim+1):
            if j%penny[0]==0:
                dp[0][j]=1
        for i in range(n):
            dp[i][0]=1
        for j in range(1,aim+1):
            for i in range(1,n):
                k = 0             # 注意编程中尽量不要使用重复变量，产生新的变量前需要检查是否已经被使用。
                while k*penny[i]<=j:
                    dp[i][j]+=dp[i-1][j-k*penny[i]]
                    k+=1
        return dp[n-1][aim]