Leetcode Link: 无，算法课题目
题目
arr是货币数组，其中的值都是正数。再给定一个正数aim。
每个值都认为是一张货币，
认为值相同的货币没有任何不同，
返回组成aim的方法数
例如：arr = {1,2,1,1,2,1,2}，aim = 4 方法：1+1+1+1、1+1+2、2+2 一共就3种方法，所以返回3
从暴力递归到动态规划
其实就相当于零钱兑换II 中提前收集每个面值的张数
如果想 排序直接变成零钱兑换III，结果一定是不对的。
暴力递归
def main(arr, aim):
money = list(set(arr))
counts = # 每个面值的张数，
return process(money, nums, 0, aim)
def process(money, counts, idx, rest):
if idx == len(money)
if rest == 0:
return 1
else:
return 0
res = 0
for n in range(counts[idx]+1):
if rest-n*monry[idx] >= 0:
res += process(money, nums, idx+1, rest-n*monry[idx])
return res动态规划
观察位置依赖关系
假设 i 号面值 3 元，有 2 张，求 rest = 14 的时候依赖 a,b,c三个位置
而我们考虑隔壁的⭐位置时候，它是依赖的是 b, c, d 三个位置 显然，如果像之前的硬加，是会算重一个的（数量是有限制的，所以⭐号还会依赖5元的位置），
那么我们就单独减去一个就行，即
✅= ⭐+ a - d
但是要考虑d这个位置存在不存在，要是越界了，两者就相等了。
这是多重背包问题吗？