零钱兑换III

Leetcode Link: 无，算法课上的问题

题目

arr 是货币数组，其中的值都是正数。再给定一个正数 aim。 每个值都认为是一张货币 即便是值相同的货币也认为每一张都是不同的， 返回组成 aim 的方法数 例如：arr={1,1,1}, aim=2 第0个和第1个能组成2，第1个和第2个能组成2，第0个和第2个能组成2 一共就3种方法，所以返回3

从暴力递归到动态规划

典型的从左到右的尝试模型，从左到右尝试 arr

子问题可以是返回[idx… n]上凑成 rest 的方法数

每个子问题只有如下两种情况

1. 要当前位的凑
2. 不要当前位的凑

def main(arr, aim):
	return process(arr, 0, aim)
 
def process(arr, idx, rest):
	if rest == 0:
		return 1
	
	if rest < 0 or (rest > 0 and idx == len(arr)):
		return 0
 
	p1 = process(arr, idx+1, rest)
	p2 = process(arr, idx+1, rest-arr[idx])
	return p1 + p2	

动态规划

显然只有两个可变参数

代码待确认

def main(arr, aim):
	dp = [[0 for _ in range(aim+1)] for _ in range(len(arr)+1)]
 
	for i in range(len(arr)):
		dp[i][0] = 1
 
	for i in range(len(arr)-1, -1, -1):
		for j in range(aim+1):
			
			dp[i][j] = process(arr, idx+1, rest)
			if rest-arr[idx] >= 0:
				dp[i][j] += process(arr, idx+1, rest-arr[idx])
			
 
	return dp[0][aim]

启发和联系