LeetCode 2787.将一个数字表示成幂的和的方案数：经典01背包

【LetMeFly】2787.将一个数字表示成幂的和的方案数：经典01背包

力扣题目链接：https://leetcode.cn/problems/ways-to-express-an-integer-as-sum-of-powers/

给你两个 正 整数 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 <= 300
• 1 <= x <= 5

解题方法：动态规划(01背包)

这道题可以翻译为：$t^x$组成的数组中选择一些和为$n$的数有多少种方案。

可以使用$dp[i]$代表和为$i$的方案数，初始值$dp[0]=1$，$dp[\mathrm{1..}n]=0$。

第一层循环从数组中取数，第二层循环倒序遍历dp数组且有状态转移方程$dp[i]+=dp[i-p]$，其中$p$是数组中的一个$t^x$。倒序是为了得到$dp[i]$时保证$dp[i-p]$在第二层循环中还未被更改过。

• 时间复杂度$O(n\times \sqrt[x]{n})$
• 空间复杂度$O(n)$

AC代码

C++

C++代码使用了快速幂，因数据范围很小所以浮点数pow也不会出现精度误差，若不想写快速幂也可以直接删掉int pow()函数。

/** @Author: LetMeFly* @Date: 2025-08-12 09:48:56* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-08-12 21:33:24*/
// dp[i]: 和为i的方案数
class Solution {
private:static const long long MOD = 1e9 + 7;int pow(int a, int b) {long long ans = 1;while (b) {if (b & 1) {ans = ans * a;}a = a * a;b >>= 1;}return ans;}
public:int numberOfWays(int n, int x) {vector<int> dp(n + 1);dp[0] = 1;for (int th = 1; ; th++) {int p = pow(th, x);if (p > n) {break;}for (int i = n; i >= p; i--) {dp[i] = (dp[i] + dp[i - p]) % MOD;}}return dp.back();}
};

Python

'''
Author: LetMeFly
Date: 2025-08-12 09:48:56
LastEditors: LetMeFly.xyz
LastEditTime: 2025-08-12 21:37:06
'''
class Solution:def numberOfWays(self, n: int, x: int) -> int:dp = [1] + [0] * nth = 1while True:p = th ** xif p > n:breakth += 1for i in range(n, p - 1, -1):dp[i] += dp[i - p]return dp[-1] % 1000000007

Java

/** @Author: LetMeFly* @Date: 2025-08-12 09:48:56* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-08-12 21:50:02*/
import java.util.List;
import java.util.ArrayList;class Solution {public int numberOfWays(int n, int x) {long[] dp = new long[n + 1];dp[0] = 1;for (int th = 1; ; th++) {int p = (int)Math.pow(th, x);if (p > n) {break;}for (int i = n; i >= p; i--) {dp[i] += dp[i - p];}}return (int)(dp[n] % 1000000007);}
}

Go

/** @Author: LetMeFly* @Date: 2025-08-12 09:48:56* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-08-12 21:42:16*/
package mainimport "math"func pow2787(a, b int) int {return int(math.Pow(float64(a), float64(b)))
}func numberOfWays(n int, x int) int {dp := make([]int, n + 1)dp[0] = 1for th := 1; ; th++ {p := pow2787(th, x)if p > n {break}for i := n; i >= p; i-- {dp[i] += dp[i - p]}}return dp[n] % 1000000007
}

Rust

/** @Author: LetMeFly* @Date: 2025-08-12 09:48:56* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-08-12 22:00:07*/
impl Solution {pub fn number_of_ways(n: i32, x: i32) -> i32 {let n: usize = n as usize;let mut dp: Vec<i32> = vec![0; n + 1];dp[0] = 1;for th in 1usize.. {let p: usize = th.pow(x as u32);if p > n {break;}for i in (p..=n).rev() {dp[i] = ((dp[i] as i64 + dp[i - p] as i64) % (1000000007 as i64)) as i32}}dp[n]}
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源