1. 二维dp
   dp数组的含义：用前i个硬币，能凑成j元的最小硬币个数

   #
   # 最少货币数
   # @param arr int整型一维数组 the array
   # @param aim int整型 the target
   # @return int整型
   #
   class Solution:
    def minMoney(self , arr , aim ):
        # write code here
        dp = [[i for i in range(aim+1)] for _ in range(len(arr)+1)]
        if aim <= 0 or not arr:
            return 0
   
   
   

    for j in range(len(dp[0])):
        dp[0][j] = float("inf")
    for i in range(len(dp)):
        dp[i][0] = 0

    for i in range(1, len(dp)):
        for j in range(1, len(dp[0])):
            if j-arr[i-1] >= 0:                    
                dp[i][j] = min(dp[i][j-arr[i-1]] + 1, dp[i-1][j])
            else:
                dp[i][j] = dp[i-1][j]

    if dp[-1][-1] == float("inf"):
        return -1
    else:
        return dp[-1][-1]

2. 状态压缩至一维

最少货币数

@param arr int整型一维数组 the array

@param aim int整型 the target

@return int整型

class Solution:
def minMoney(self , arr , aim ):
# write code here
dp = [i for i in range(aim+1)]
if aim <= 0 or not arr:
return 0
for i in range(len(dp)):
dp[i] = float("inf")
dp[0] = 0

    for i in range(len(arr)):
        for j in range(1, len(dp)):
            if j-arr[i-1] >= 0:                    
                dp[j] = min(dp[j-arr[i-1]] + 1, dp[j])
            else:
                dp[j] = dp[j]

    if dp[-1] == float("inf"):
        return -1
    else:
        return dp[-1]

```