Medium

题目描述

给你两个正整数 n 和 x。

返回将 n 表示为一些 互不相同 正整数的 x 次幂之和的方案数。换句话说，返回互不相同整数 [n1, n2, ..., nk] 的集合数目，使得 n = n1^x + n2^x + ... + nk^x。

由于结果可能非常大，返回它对 10^9 + 7 取余的结果。

例如，如果 n = 160 且 x = 3，表示 n 的一种方法是 n = 2^3 + 3^3 + 5^3。

示例 1：

输入：n = 10, x = 2
输出：1
解释：我们可以将 n 表示为：n = 3^2 + 1^2 = 10。
可以证明将 10 表示为不同整数 2 次幂之和的唯一方案是上述方案。

示例 2：

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

提示：

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

解题思路

这是一道经典的动态规划问题，类似于"背包问题"的变种。

思路分析：

我们需要找到所有可能的方案，将 n 表示为互不相同正整数的 x 次幂之和。由于数字必须互不相同，这类似于"0-1背包问题"，每个数字最多只能使用一次。

动态规划状态定义：

  • dp[i][j] 表示使用前 i 个正整数（1到i），能够组成和为 j 的方案数
  • 对于每个数字 i，我们有两种选择：
    1. 不使用数字 i：方案数为 dp[i-1][j]
    2. 使用数字 i：方案数为 dp[i-1][j-i^x]（前提是 j >= i^x）

状态转移方程：

dp[i][j] = dp[i-1][j] + (j >= i^x ? dp[i-1][j-i^x] : 0)

优化： 由于我们只需要前一行的状态，可以使用一维数组进行空间优化。注意要从后向前更新，避免重复使用当前行的值。

边界条件：

  • dp[0] = 1：和为0的方案数为1（不选任何数）
  • 当 i^x > n 时，可以提前结束，因为更大的数字不可能被使用

时间复杂度为 O(k×n)，其中 k 是满足 k^x ≤ n 的最大正整数。空间复杂度为 O(n)。

代码实现

class Solution {
public:
    int numberOfWays(int n, int x) {
        const int MOD = 1e9 + 7;
        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        
        for (int i = 1; ; i++) {
            int power = 1;
            for (int j = 0; j < x; j++) {
                power *= i;
                if (power > n) break;
            }
            if (power > n) break;
            
            for (int j = n; j >= power; j--) {
                dp[j] = (dp[j] + dp[j - power]) % MOD;
            }
        }
        
        return dp[n];
    }
};

class Solution:
    def numberOfWays(self, n: int, x: int) -> int:
        MOD = 10**9 + 7
        dp = [0] * (n + 1)
        dp[0] = 1
        
        i = 1
        while True:
            power = i ** x
            if power > n:
                break
            
            for j in range(n, power - 1, -1):
                dp[j] = (dp[j] + dp[j - power]) % MOD
            
            i += 1
        
        return dp[n]

public class Solution {
    public int NumberOfWays(int n, int x) {
        const int MOD = 1000000007;
        int[] dp = new int[n + 1];
        dp[0] = 1;
        
        for (int i = 1; ; i++) {
            long power = 1;
            for (int j = 0; j < x; j++) {
                power *= i;
                if (power > n) break;
            }
            if (power > n) break;
            
            for (int j = n; j >= power; j--) {
                dp[j] = (dp[j] + dp[j - (int)power]) % MOD;
            }
        }
        
        return dp[n];
    }
}

var numberOfWays = function(n, x) {
    const MOD = 1e9 + 7;
    const dp = new Array(n + 1).fill(0);
    dp[0] = 1;
    
    for (let i = 1; ; i++) {
        const power = Math.pow(i, x);
        if (power > n) break;
        
        for (let j = n; j >= power; j--) {
            dp[j] = (dp[j] + dp[j - power]) % MOD;
        }
    }
    
    return dp[n];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(k×n)k是满足k^x ≤ n的最大正整数，通常k ≪ n
空间复杂度O(n)使用一维dp数组存储状态

相关题目