动态规划经典三题_完全平方数
279. 完全平方数
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
示例 1：
输入：n = 12 输出：3 解释：12 = 4 + 4 + 4示例 2：
输入：n = 13 输出：2 解释：13 = 4 + 9
@cache # 缓存装饰器，避免重复计算 dfs 的结果（记忆化）
def dfs(i: int, j: int) -> int:if i == 0:return inf if j else 0if j < i * i:return dfs(i - 1, j) # 只能不选return min(dfs(i - 1, j), dfs(i, j - i * i) + 1) # 不选 vs 选class Solution:def numSquares(self, n: int) -> int:return dfs(isqrt(n), n)322. 零钱兑换
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
示例 2：
输入：coins =
[2], amount =3输出：-1
示例 3：
输入：coins = [1], amount = 0
输出：0
class Solution:def coinChange(self, coins: List[int], amount: int) -> int:n = len(coins)f = [[inf] * (amount + 1) for _ in range(2)]f[0][0] = 0for i, x in enumerate(coins):for c in range(amount + 1):if c < x:f[(i + 1) % 2][c] = f[i % 2][c]else:f[(i + 1) % 2][c] = min(f[i % 2][c], f[(i + 1) % 2][c - x] + 1)ans = f[n % 2][amount]return ans if ans < inf else -12787. 将一个数字表示成幂的和的方案数
给你两个正整数 n 和 x 。
请你返回将 n 表示成一些 互不相同 正整数的 x 次幂之和的方案数。换句话说，你需要返回互不相同整数 [n1, n2, ..., nk] 的集合数目，满足 n = n1x + n2x + ... + nkx 。
由于答案可能非常大，请你将它对 109 + 7 取余后返回。
比方说，n = 160 且 x = 3 ，一个表示 n 的方法是 n = 23 + 33 + 53 。
示例 1：
输入：n = 10, x = 2 输出：1 解释：我们可以将 n 表示为：n = 32 + 12 = 10 。 这是唯一将 10 表达成不同整数 2 次方之和的方案。示例 2：
输入：n = 4, x = 1 输出：2 解释：我们可以将 n 按以下方案表示： - n = 41 = 4 。 - n = 31 + 11 = 4 。
class Solution:def numberOfWays(self, n: int, x: int) -> int:f = [1] + [0] * nfor i in range(1, n + 1):v = i ** xif v > n:breakfor s in range(n, v - 1, -1):f[s] += f[s - v]return f[n] % 1_000_000_007