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

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

思路

01 背包

解题过程

定义 dp[j] 表示对于第 i 个合法数字的 x 次方，选择它后的方法数。省略了不选择时候的传递，降低了数组的维度。

复杂度

• 时间复杂度: $O(n^2)$

• 空间复杂度: $O(n)$

Code

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