2787. 将一个数字表示成幂的和的方案数（Rating 1817）

以下内容偏向于记录个人练习过程及思考，非常规题解内容

题目

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

Rating 1817

思路

典型0-1背包问题

其中从1到n为n个物品，每个数字的x次方表示该物品的体积，背包总容量为n

选/不选每个物品，使用动态规划解决。

代码

二维数组写法

class Solution:
    def numberOfWays(self, n: int, x: int) -> int:
        nums = []
        for i in range(1, n + 1): # 将可能的数字预处理出来
            if i ** x > n: # 一定是小于等于n的
                break
            nums.append(i ** x)
        MOD = 10 ** 9 + 7
        m = len(nums) # 共m个物品
        # dp[i][j] 表示前i个数字和为j的方案数，注意对于背包问题：1 <= i <= m, 0 <= j <= n
        dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
        dp[0][0] = 1 # 初始化，前0个数字和为0的方案数是1
        for i in range(1, m + 1):
            for j in range(0, n + 1):
                dp[i][j] = dp[i - 1][j] # 不选第i个物品
                if j >= nums[i - 1]:
                    dp[i][j] = (dp[i][j] + dp[i - 1][j - nums[i - 1]]) % MOD # 选第i个物品
        return dp[m][n]

一维数组写法

由于第i行的dp[i][j]仅与第i - 1行的dp[i - 1][j]和dp[i - 1][j - nums[i - 1]]有关，即仅与上一行的当前列和较小的列有关。

因此可以优化为一维数组，从大到小倒序遍历j这一维（因为先更新较大的列不会影响更新较小的列），减少空间复杂度。

class Solution:
    def numberOfWays(self, n: int, x: int) -> int:
        nums = []
        for i in range(1, n + 1):
            if i ** x > n:
                break
            nums.append(i ** x)
        MOD = 10 ** 9 + 7
        m = len(nums)
        dp = [0 for _ in range(n + 1)]
        dp[0] = 1
        for i in range(1, m + 1):
            for j in range(n, nums[i - 1] - 1, -1): # 倒序。因为倒序，也可以省掉一个if
                dp[j] = (dp[j] + dp[j - nums[i - 1]]) % MOD
        return dp[n]