What pattern does this problem follow in dynamic programming?

It follows state transition dynamic programming, where each state represents the number of ways to reach a sum with unique xth powers.

Why must the DP array be updated from high to low?

Updating from high to low ensures each integer is counted at most once, preserving uniqueness in combinations.

How does modulo 10^9 + 7 affect the solution?

All additions are done modulo 10^9 + 7 to prevent integer overflow and match problem constraints.

Can this method handle n = 300 and x = 5 efficiently?

Yes, because the DP array scales linearly with n and only considers integers whose xth powers are <= n.

How do I extend this solution to find the actual sets?

You can modify the DP table to store lists of combinations, but this increases memory and complexity significantly.

#2787

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

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

给你两个正整数 n 和 x 。请你返回将 n 表示成一些互不相同正整数的 x 次幂之和的方案数。换句话说，你需要返回互不相同整数 [n 1 , n 2 , ..., n k ] 的集合数目，满足 n = n 1 x + n 2 x + ... + n k x 。由于答案可能非常大，请你将…

动态规划

题目描述

给你两个正整数 n 和 x 。

请你返回将 n 表示成一些 互不相同 正整数的 x 次幂之和的方案数。换句话说，你需要返回互不相同整数 [n₁, n₂, ..., n_k] 的集合数目，满足 n = n₁^x + n₂^x + ... + n_k^x 。

由于答案可能非常大，请你将它对 10⁹ + 7 取余后返回。

比方说，n = 160 且 x = 3 ，一个表示 n 的方法是 n = 2³ + 3³ + 5³。

示例 1：

输入：n = 10, x = 2
输出：1
解释：我们可以将 n 表示为：n = 3² + 1² = 10 。
这是唯一将 10 表达成不同整数 2 次方之和的方案。

示例 2：

输入：n = 4, x = 1
输出：2
解释：我们可以将 n 按以下方案表示：
- n = 4¹ = 4 。
- n = 3¹ + 1¹ = 4 。

提示：

1 <= n <= 300
1 <= x <= 5

lightbulb

解题思路

方法一：动态规划

我们定义 $f[i][j]$ 表示在前 $i$ 个正整数中选取一些数的 $x$ 次幂之和等于 $j$ 的方案数，初始时 $f[0][0] = 1$ ，其余均为 $0$ 。答案为 $f[n][n]$ 。

对于每个正整数 $i$ ，我们可以选择不选它或者选它：

不选它：此时方案数为 $f[i-1][j]$ ；
选它：此时方案数为 $f[i-1][j-i^x]$ （前提是 $j \geq i^x$ ）。

因此状态转移方程为：

f[i][j] = f[i-1][j] + (j \geq i^x ? f[i-1][j-i^x] : 0)

注意到答案可能非常大，我们需要对 $10^9 + 7$ 取余。

时间复杂度 $O(n^2)$ ，空间复杂度 $O(n^2)$ 。其中 $n$ 是题目中给定的整数。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def numberOfWays(self, n: int, x: int) -> int:
        mod = 10**9 + 7
        f = [[0] * (n + 1) for _ in range(n + 1)]
        f[0][0] = 1
        for i in range(1, n + 1):
            k = pow(i, x)
            for j in range(n + 1):
                f[i][j] = f[i - 1][j]
                if k <= j:
                    f[i][j] = (f[i][j] + f[i - 1][j - k]) % mod
        return f[n][n]

speed

复杂度分析

指标	值
时间	complexity is O(n * n^(1/x)) due to iterating all possible integers whose xth power is <= n and updating dp. Space complexity is O(n) since only a one-dimensional DP array is needed.
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
Focus on unique usage of integers to avoid overcounting in the DP table.
question_mark
Emphasize proper iteration order for state transitions to ensure correctness.
question_mark
Clarify handling of modulo arithmetic to prevent integer overflow.

warning

常见陷阱

外企场景

error
Using integers multiple times instead of enforcing uniqueness.
error
Iterating dp array from low to high, which breaks the uniqueness constraint.
error
Failing to apply modulo 10^9 + 7 correctly in each update step.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Count combinations allowing repeated integers (classic coin change variant).
arrow_right_alt
Compute the number of ways to express n as sum of factorials instead of powers.
arrow_right_alt
Extend the problem to find all actual sets, not just the count.

help

常见问题

外企场景

继续练习

#2786 访问数组中的位置使分数最大 #2791 树中可以形成回文的路径数 #2801 统计范围内的步进数字数目