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

🟠   🔖  动态规划  🔗 力扣 LeetCode

题目

Given two positive integers n and x.

Return the number of waysn can be expressed as the sum of the xthpower 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	目标和	[✓]	数组 动态规划 回溯	🟠	🀄️ 🔗