leetcode-硬币问题

2020-04-23

链接：https://leetcode-cn.com/problems/coin-lcci

硬币。给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。(结果可能会很大，你需要将结果模上1000000007)

示例1:

输入: n = 5
输出：2
解释: 有两种方式可以凑成总金额:
5=5
5=1+1+1+1+1

示例2:

输入: n = 10
输出：4
解释: 有四种方式可以凑成总金额:
10=10
10=5+5
10=5+1+1+1+1+1
10=1+1+1+1+1+1+1+1+1+1

解决思路：

动态规划

定义 f(i, v) 表示前 i 种硬币构成面值为 v 的方案数，用 c[i] 表示第 i 种硬币面值

则
$$
f(i,v) = f(i-1, v-0 c[i]) + f(i-1, v-1c[i]) + … + f(i-1, v-kc[i])
$$
其中
$$
k<= v/c[i]
$$
举例说明： c={1,5,10,25}, 当i=4时，c[i]=25, 如果我们求前4种硬币构成50的方案数，则
$$
f(4, 50) = f(3, 50) + f(3, 50-125) + f(3, 50-225)
$$
优化
$$
f(i, v-c[i]) = f(i-1, v-c[i]) + f(i-1, v-2c[i]) + … + f(i-1, v-k*c[i])
$$
得到化简后的方程：
$$
f(i,v) = f(i-1, v) + f(i, v-c[i])
$$

class Solution:
	def waysToChange(self, n):
		mod = 10 ** 9 + 7
		coins = [25, 10, 5, 1]
		
		f = [1] + [0] * n
		for coin in coins:
			for i in range(coin, n+1):
				f[i] += f[i - coin]
		return f[n] % mod