动态规划题解_将一个数字表示成幂的和的方案数【LeetCode】

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 。

一、算法逻辑（逐步思路）

❓ 题目描述：

给定两个整数 n 和 x，问：
有多少种方法可以用不同的正整数的 x 次幂相加，恰好等于 n？

• 每个整数最多使用一次（不能重复）；
• 返回方案数，结果对 10^9 + 7 取模。

---

✅ 解析过程：

1. 状态定义：

• 定义 f[s] 表示和为 s 的组合数目；
• 初始化：f[0] = 1，表示选法为空时和为 0 的唯一方案。

2. 状态转移：

• 对每个正整数 i，计算它的 x 次幂 v = i^x；
• 使用这个数能更新哪些和 s？

• • 遍历 s 从 n 到 v（倒序，防止重复使用）；
  • 更新方式：f[s] += f[s - v]

• • • 意思是：若当前组合中加入一个 v，使得和达到 s，那就看以前有多少种方法能组成 s - v；
    • 相当于经典的0/1 背包模型（每个数最多使用一次）。

3. 终止条件：

• 如果当前的 i^x > n，说明无法再用于任何组合，直接退出。

4. 返回值：

• f[n] 表示最终组成 n 的合法组合数；
• 对结果取模是为了防止整数溢出。

---

二、算法核心点

✅ 核心思想：0/1背包模型上的指数幂优化

• 每个正整数 i 只能使用一次，对应背包问题中“每种物品最多取 1 次”；
• 数字 v = i^x 就是物品的“体积”；
• 每次用 f[s] += f[s - v] 实现状态转移；
• 为避免重复计算、实现“每个数最多选一次”，必须倒序更新状态数组。

对应题目经典名称：

Perfect Powers Combination Problem（幂次组合计数）

class Solution:def numberOfWays(self, n: int, x: int) -> int:f = [1] + [0] * n  # 初始化DP数组：f[s] 表示组成和为 s 的方案数# 初始状态：f[0] = 1，表示“和为0”的方案就是啥也不选for i in range(1, n + 1):  # 枚举所有底数 i（1 到 n）v = i ** x  # 当前考虑的数是 i 的 x 次幂if v > n:   # 如果这个数太大，跳出循环break# 倒序遍历（0/1背包）从 n 到 vfor s in range(n, v - 1, -1):f[s] += f[s - v]  # 转移方程：将 v 加入组合中，组成 sreturn f[n] % 1_000_000_007  # 返回最终和为 n 的方案数

三、复杂度分析

• 时间复杂度：O(k × n)

• • k 是最多可以选择的整数个数（即 i 满足 i^x ≤ n）；
  • 对每个合法 i，我们进行一次 O(n) 的遍历。

• 空间复杂度：O(n)

• • 状态数组 f 长度为 n + 1。

---

总结表：

维度	内容
✅ 思路逻辑	将问题转换为组合数问题，用 0/1 背包方式动态转移
✅ 核心技巧	每个数最多用一次（倒序遍历）；幂次作为体积；经典 f[s] += f[s - v] 模型
✅ 时间复杂度	O(√n × n) 最多枚举 √n 个底数，每次遍历 n 个状态
✅ 空间复杂度	O(n) 一维 DP 数组

总结思路：

步骤	内容
初始化 f[0] = 1	和为 0 有 1 种方式（空集）
枚举 i = 1...n	将 i 的 x 次幂作为候选数
倒序更新 DP 数组	保证每个数最多用一次（0/1背包）
更新 f[s] += f[s - v]	表示：新方案 = 旧方案 + 使用 v 的方案
取模	避免大数溢出