给定数组arr，arr中所有的值都为正整数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个aim，代表要找的钱数，求组成aim的最少货币数。
如果无解，请返回-1.
数据范围：数组大小满足 100000 ≤ n ≤ 10000 ， 数组中每个数字都满足 0 < val ≤ 10000，0≤aim≤5000
要求：时间复杂度 O(n×aim) ，空间复杂度 O(aim)。
思路：动态规划
定义 dp(a) 表示凑出 a 元钱需要最小的零钱数量；
则 dp(a) = min(dp(a), dp(a - arr[j]) + 1) for j in range(len(arr))；
TODO: 整理完全背包相关内容；
Python
class Solution:
def minMoney(self , arr: List[int], aim: int) -> int:
import sys
sys.setrecursionlimit(100000)
from functools import lru_cache
@lru_cache(maxsize=None)
def dp(a): # 凑出 a 元钱需要最小的零钱数量
if a == 0:
return 0
ret = float('inf')
for i in range(len(arr)): # 对每种面值
if a >= arr[i]:
# 如果 a 大于当前零钱面值；
# 则先兑换一张该面值的零钱，然后计算剩余钱数的最小零钱数量；
# 记录所有可能中的最小值
ret = min(ret, dp(a - arr[i]) + 1)
return ret
ret = dp(aim)
return -1 if ret == float('inf') else ret