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] * n
        th = 1
        while True:
            p = th ** x
            if p > n:
                break
            th += 1
            for 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 main

import "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] = 1
    for 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和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源