↓Skip to main content
  1. Posts/

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

·1 min·
Table of Contents

LeetCode-2787 将一个数字表示成幂的和的方案数 #

Solution 1 #

0-1 背包问题的变形.

代码如下:

class Solution:
    def numberOfWays(self, n: int, x: int) -> int:
        MOD = int(1e9 + 7)
        dp = [1] + [0] * n
        for i in range(1, n + 1):
            v = i ** x
            if v > n:
                break
            for s in range(n, v - 1, -1):
                dp[s] = (dp[s] + dp[s - v]) % MOD
        return dp[n]