【Leetcode Daily】2787将一个数字表示成幂的和的方案数

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，就是给正整数 n 和 x，要求有多少无重复正整数数字的 x 次方之和恰好为 n。

思路分享

• 01 背包题目，核心就是 选或不选 的思想，如果选了当前的值（要先判断选择是否合法，否则直接不选），那么就要更新剩余可以用的空间；不选则直接到下一个物品来判断。

  https://leetcode.cn/problems/ways-to-express-an-integer-as-sum-of-powers/solutions/2354970/0-1-bei-bao-mo-ban-ti-by-endlesscheng-ap09/

代码解答（强烈建议自行解答后再看）

• 参考题解

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