动态规划经典三题_完全平方数

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 -1

2787. 将一个数字表示成幂的和的方案数

给你两个正整数 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