标签: 动态规划
难度: Medium
给你两个 正 整数 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 。
提示：
1 <= n <= 3001 <= x <= 5运行时间: 53 ms
内存: 16.0 MB
MX_N, MX_X = 300, 5
f = [[1] + [0] * MX_N for _ in range(MX_X)]
for x in range(MX_X):
for i in count(1):
v = i ** (x + 1)
if v > MX_N: break
for s in range(MX_N, v - 1, -1):
f[x][s] += f[x][s - v]
class Solution:
def numberOfWays(self, n: int, x: int) -> int:
return f[x - 1][n] % (10 ** 9 + 7)
题解使用了动态规划的方式来解决问题。动态规划数组 f[x][n] 表示使用1到x+1次幂的和来表示数字n的方案数。初始状态是每个f[x][0]为1，因为表示0的方案只有一种，即不选择任何数字。对于每个x次幂，遍历所有可能的底数i，计算出i的x+1次方v，如果v大于n则中断该轮循环。接着，对于每个s>=v，更新f[x][s]，使其加上f[x][s-v]的值，意味着对于每个可能的v，都尝试将其加入到之前计算的结果中去。这样，每个f[x][n]最终存储了使用1到x+1次幂的和来表达n的所有方案数。
时间复杂度: O(n * x * maxBase)
空间复杂度: O(x * n)
# 动态规划数组初始化，x取值为0到4，n取值为0到300
MX_N, MX_X = 300, 5
f = [[1] + [0] * MX_N for _ in range(MX_X)]
# 外层循环针对每个x，内层循环计算可能的i的x+1次幂v
for x in range(MX_X):
for i in count(1):
v = i ** (x + 1)
if v > MX_N: break
# 更新动态规划数组，从大到小更新防止重复使用同一个幂次
for s in range(MX_N, v - 1, -1):
f[x][s] += f[x][s - v]
class Solution:
def numberOfWays(self, n: int, x: int) -> int:
# 返回n表示成x次幂之和的方案数，结果模10^9+7
return f[x - 1][n] % (10 ** 9 + 7)
在此题解中，动态规划数组 f[x][n] 表示使用从1次幂到(x+1)次幂的所有幂次的和来表示数字 n 的方案数。维度 x 代表幂的次数（1到x+1），而维度 n 代表目标数字。之所以选择这样的维度，是为了能够逐步构建每个数字的表示方法，同时考虑不同的幂次。通过这种方式，可以逐渐增加幂的次数，从而找到所有可能的表示方法。
动态规划初始化为 f[x][0] = 1 是因为表示数字0的唯一方法是不使用任何数的幂，这相当于一个空集的和。也就是说，不论幂次数如何，都存在一个方案来表达数字0，即不选择任何项。对于其他元素 f[x][n] (n > 0)，它们被初始化为0，因为在开始的时候，没有找到任何用于表达这些数字的幂和方案，这些值将在算法的迭代过程中被更新。
为了避免重复计算同一个数的幂次，动态规划的更新是从大到小进行的。具体来说，对于每一个幂次 v，数组的更新是从 n 向下至 v 进行。这样做的好处是，每次更新 f[x][s] 时，加入的 f[x][s-v] 是在这一轮更新之前就已经确定的值，而不是在当前轮次中更新过的值。因此，每个幂次只会被计算一次，避免了多次使用同一幂次的问题。