换钱的最少货币数

有点难理解，其实还是递归，https://www.jianshu.com/p/b9d7ff91684e

i: 代表可以使用的货币种类为 arr[0..i]
j: 代表需要兑换的面值数，其取值范围为[0..aim]，因此实现时，二维数组的列数应该为aim + 1
对于dp[i][j]，更新的依据有两个值，一个是“不使用当前种类的货币时，组成总数的j的最小方法，即dp[i-1][j]”，另外一个是“使用并且仅使用一张当前种类的货币时，组成总数的j的最小方法，即 dp[i][j-arr[i]] + 1”，取这两个值中的最小值即为dp[i][j]的值。
上面的实现，需要的空间复杂度是O(N * aim)，下面的方法，可以将空间复杂度优化到O(aim)。
优化方法：
生成一个一维动态规划数组dp[aim + 1]
构造初始值：参考上面的方法，初始值表示只使用arr[0]一种货币时，兑换[0..aim]的最少货币数。
更新动态规划表：更新方向，从左到右更新。对于dp[j]，更新的依据有两个，一个是 dp[j]（old），换算成二维数组，即为不使用arr[j]货币时的最少货币数，即为dp[line-1][j]。另外一个是dp[j-arr[j]] + 1，即为“使用并且仅使用一张当前种类的货币时的最少货币数”，换算成二维数组，即为dp[line][j-arr[j]] + 1.

#
# 最少货币数
# @param arr int整型一维数组 the array
# @param aim int整型 the target
# @return int整型
#
class Solution:
    def minMoney(self, arr, aim):
        # write code here
        N=len(arr)
        dp = [float('inf')]*(aim+1)
        dp[0] = 0
        for i in range(1, aim+1):
            for j in range(N):
                if i < arr[j]:
                    continue
                dp[i] = min(dp[i], dp[i-arr[j]]+1)                
        if dp[aim] == float('inf'):
            return -1 
        else:
            return dp[aim]