2787.md

title	description	keywords
2787. 将一个数字表示成幂的和的方案数	LeetCode 2787. 将一个数字表示成幂的和的方案数题解，Ways to Express an Integer as Sum of Powers，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。	LeetCode 2787. 将一个数字表示成幂的和的方案数 将一个数字表示成幂的和的方案数 Ways to Express an Integer as Sum of Powers 解题思路 动态规划

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

🟠 Medium  🔖  动态规划  🔗 力扣 LeetCode

题目

Given two positive integers n and x.

Return the number of waysn can be expressed as the sum of the xth power of unique positive integers, in other words, the number of sets of unique integers [n1, n2, ..., nk] where n = n1x + n2x + ... + nkx .

Since the result can be very large, return it modulo 10^9 + 7.

For example, if n = 160 and x = 3, one way to express n is n = 23 + 33 - 53.

Example 1:

Input: n = 10, x = 2

Output: 1

Explanation: We can express n as the following: n = 32 + 12 = 10.

It can be shown that it is the only way to express 10 as the sum of the 2nd power of unique integers.

Example 2:

Input: n = 4, x = 1

Output: 2

Explanation: We can express n in the following ways:

• n = 41 = 4.
• n = 31 + 11 = 4.

Constraints:

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

题目大意

给你两个 正 整数 n 和 x 。

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

由于答案可能非常大，请你将它对 10^9 + 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 <= 300
• 1 <= x <= 5

解题思路

本题要求计算可以用不同整数的 x 次幂之和表示 n 的不同方案数。
我们可以将其转换为 背包问题（完全背包），即：

• n 是背包的容量。
• i^x（i 的 x 次幂）是可选的物品。
• 目标是求出能填满 n 的不同组合方式。

1. 定义状态 dp[j] 表示填满 j 这个目标数的方案数。

2. 状态转移

   • 对于每个 i（从 1 开始），计算 pow = i^x。
   • 从 n 递减遍历 j，如果 j >= pow，则可以选择使用 pow：
     • dp[j] = (dp[j] + dp[j - pow]) % mod
     • 其中 dp[j - pow] 代表去掉 pow 之前的方案数。

3. 初始化 dp[0] = 1，表示填满 0 只有一种方式（什么都不选）。

4. 计算顺序

   • i 从 1 开始递增，直到 i^x > n，确保 i^x 不会超过 n。
   • j 采用 倒序遍历，避免重复使用相同的 i^x。

5. 取模运算：由于结果可能很大，每次更新 dp[j] 时需要 % 10^9+7。

复杂度分析

• 时间复杂度：O(n^(1/x) * n)，外层 i 的范围为 O(n^(1/x))，内层遍历 O(n)。
• 空间复杂度：O(n)，使用 dp 数组存储状态。

代码

/**
 * @param {number} n
 * @param {number} x
 * @return {number}
 */
var numberOfWays = function (n, x) {
	const mod = Math.pow(10, 9) + 7;
	const dp = new Array(n + 1).fill(0);
	dp[0] = 1;
	for (let i = 1; Math.pow(i, x) <= n; i++) {
		let pow = Math.pow(i, x);
		for (let j = n; j >= pow; j--) {
			dp[j] = (dp[j] + dp[j - pow]) % mod;
		}
	}
	return dp[n];
};

相关题目

题号	标题	题解	标签	难度	力扣
279	完全平方数	[✓]	广度优先搜索 数学 动态规划	🟠	🀄️ 🔗
377	组合总和 Ⅳ	[✓]	数组 动态规划	🟠	🀄️ 🔗
494	目标和	[✓]	数组 动态规划 回溯	🟠	🀄️ 🔗