Leetcode 2787. Ways to Express an Integer as Sum of Powers

[Woodyiiiiiii]

2787. Ways to Express an Integer as Sum of Powers

2787. Ways to Express an Integer as Sum of Powers

讲解：
0-1 背包模板题
赛事活动｜第 109 场双周赛 解题报告 | 珂学家 | 奇偶状态机DP + 0-1背包
0-1背包 完全背包【基础算法精讲 18】
一篇文章吃透背包问题！（细致引入+解题模板+例题分析+代码呈现）

类似题目：
518. Coin Change II
494. Target Sum
1049. Last Stone Weight II
377. Combination Sum IV

1、记忆化搜索

我比赛中使用记忆化搜索做的，不算正常解法。构建以n为长，和sum为高的二维数组作为缓存，用取或不取的策略去dfs。我WA了四次，其中前三次没有考虑到和会溢出的问题，没有用long类型来存储和；其次最后一次，记忆化缓存一开始要设置成-1而不是0，这样才能起作用。

class Solution {
    final int MOD = (int) (1e9 + 7);
    int n, x;
    long[][] memo;
    int k;

    public int numberOfWays(int n, int x) {
        this.n = n;
        this.x = x;
        // 计算以x底数，n为数的对数
        this.k = x == 1 ? n : (int) (Math.log(n) / Math.log(x));
        this.memo = new long[n + 1][n + 1];
        for (int i = 0; i <= n; i++) {
            Arrays.fill(memo[i], -1);
        }
        int ans = (int) dfs(1, 0);
        return ans;
    }

    private long dfs(int i, long sum) {
        if (sum == n) {
            return 1;
        }
        if (sum > n || i > n) {
            return 0;
        }
        if (memo[i][(int) sum] != -1) {
            return memo[i][(int) sum];
        }
        long res = dfs(i + 1, sum + (int)(Math.pow(i, x))) + dfs(i + 1, sum);
        res %= MOD;
        return memo[i][(int) sum] = res;
    }
}

2、01-背包

这道题声明每个数只能用一次(所以可以看成物品)，而且存在取/不取，所以很容易联想到0-1背包。所以这道题是经典的0-1背包计数模型。

因为每个整数只能用一次，所以是倒序遍历。

func numberOfWays(n int, x int) int {
    MOD := (int64)(1e9 + 7)
	dp := make([]int64, n+1)
	for i := 1; i <= n; i++ {
		num := (int64)(math.Pow(float64(i), float64(x)))
		if num > (int64)(n) {
			break
		}
		dp[0] = 1
		for j := (int64(n)); j >= num; j-- {
			dp[j] = (dp[j] + dp[(int)(j)-(int)(num)]) % MOD
		}
	}
	return (int)(dp[n])
}