给定数组 arr，arr 中所有的值都为正整数。每个值代表一张钱的面值，再给定一个整数 aim 代表要找的钱数，求组成 aim 的最少货币数。
举例
- arr= 【5,2,3】，aim = 20；返回 -1
- 5 元，2元，3元的钱各有 1 张，无法组成 20 元，返回默认值 -1
- arr= 【5,2,5,3】，aim = 10；返回 2
- 2 张 5 元
- arr= 【5,3】，aim=0；返回 0
- 不用任何货币就可以组成 0 元
解法一：暴力递归
f ( i,rest) 定义：使用 arr[ 0 : i+1] 的货币并且 aim = rest 时的最小货币数。
最终返回结果：f ( len(arr) - 1,aim )
可能性分类：
- 保留当前货币 arr[i] 的子问题：num1 = f( i -1, aim - arr[i] ) + 1
- 不保留当前货币 arr[i] 的子问题：num2 =f( i -1, aim )
- 决策： min(num1,num2) ：注意判断返回值的有效性（num1 != sys.maxsize），无效返回值表示此路不通，需要丢弃。
base case
- 无效参数：i < 0 or rest < 0
- 如果有货币等于 rest ，那么最小货币数为 1
def min_coins(array, aim):
return f(array, len(array) - 1, aim)
def f(array, i, rest):
# base case
# 钱不够或者硬币不够
# 钱不够了
if rest < 0: return -1
# 上一步刚等于 aim，此时不需要硬币了
if rest == 0: return 0
# aim > 0 没有硬币可用了
if i < 0:
return -1
# 不保留 arr[i]
p1 = f(array, i - 1, rest)
# 保留 arr[i]
p2 = f(array, i - 1, rest - array[i])
if p1 == -1 and p2 == -1:
return -1
elif p1 == -1 or p2 == -1:
return max(p1, p2 + 1)
return min(p1, p2 + 1)
解法二：动态规划
f 函数有两个变量
- i：货币数组的下标（在dp 中为行）
- rest：剩余钱数（在 dp 中为 列）
def min_coins2(array, aim):
if aim < 0 or not array: return -1
if aim <= 0: return 0
n = len(array)
dp = [[-1] * (aim + 1) for _ in range(n)]
# base case
if array[0] <= aim: dp[array[0]] = 1
for i in range(1, n):
for j in range(aim + 1):
left_up = 1 if array[i] == j else -1
if j - array[i] >= 0 and dp[i - 1][j - array[i]] != -1:
left_up = dp[i - 1][j - array[i]] + 1
dp[i][j] = min(left_up, dp[i - 1][j])
return dp[-1][-1]
解法二：滚动数组
滚动数组是从上向下滚动，填充充从右向左填充。
def min_coins3(array, aim):
if aim < 0 or not array: return -1
if aim <= 0: return 0
n = len(array)
dp = [sys.maxsize] * (aim + 1)
# base case
if array[0] <= aim: dp[array[0]] = 1
for i in range(1, n):
for j in range(aim, -1, -1):
# base case
left_up = 1 if array[i] == j else sys.maxsize
if j - array[i] >= 0 and dp[j - array[i]] != sys.maxsize:
left_up = dp[j - array[i]] + 1
dp[j] = min(left_up, dp[j])
return dp[-1] if dp[-1] != sys.maxsize else -1
对数器
import random
def generator_random_arr(max_size, max_value):
return [int(random.random() * max_value) + 1 for _ in range(int(random.random() * max_size) + 1)]
def check():
max_size = 10
max_value = 10
for _ in range(1000):
arr = generator_random_arr(max_size, max_value)
aim = int(random.random() * sum(arr)) + 1
res = min_coins(arr, aim)
res2 = min_coins2(arr, aim)
res3 = min_coins3(arr, aim)
if res != res2 or res != res3:
print("ERROR", "res=", res, "res2=", res2, "res3=", res3, aim, arr)
print("OVER")
check()