算法题-不同数幂和为目标数

共计 3091 个字符，预计需要花费 8 分钟才能阅读完成。

具体的题目叙述如下：

给你两个  正  整数  n  和  x 。

请你返回将  n  表示成一些   互不相同  正整数的 x  次幂之和的方案数。换句话说，你需要返回互不相同整数  [n1, n2, ..., nk]  的集合数目，满足  n = n1x + n2x + ... + nkx 。

由于答案可能非常大，请你将它对  109 + 7  取余后返回。

比方说，n = 160  且  x = 3 ，一个表示  n  的方法是  n = 23 + 33 + 53 。

示例 1：

输入：n = 10, x = 2
输出：1
解释：我们可以将 n 表示为：n = 32 + 12 = 10。这是唯一将 10 表达成不同整数 2 次方之和的方案。

我的分析

我们会收到 n 和 x，我们需要求得 有多少种不同的方案

方案：任何不同的数，它们的 x 次幂相加之和 等于 n

我们要得到 方案的种数

由此我们读懂了题目，明确了问题的目标，接下来就是分析如何实现这个问题。

首先，我想我们需要枚举，因为给定了范围，枚举的每个数都需要是 正整数。

但是枚举 需要条件 / 范围，不然，不就死循环了吗？而且也就失去解题的意义了

那么分析 / 经验，如果某个数的 x 次幂超过了 n，以及后面的数必然也超过，这些数都不能算入方案里面，所以 我们就有了循环的框架：

// 找出所有可能参与的组合的数
  for (let i = 1; i <= n; i++) {
    // 返回一个数的指数次幂 i 的 x 次
    // Math.pow(base,exponent)
    let val = Math.pow(i, x);
    // 当前枚举数的次幂
    // 如果一个数的指数次幂大于 n，则退出循环
    if (val > n) {break;}
  

那么现在，又有问题了，是每个数都能用得到吗？并不一定，该数能不能用得到，需要考虑从后向前推出来，比如 10，组成 10 的方案，从 [1,2,3] 里面找出方案，2 就用不到。

但是从前向后推，是很复杂的，但从后向前推，就是从构成 10 的成分入手，比如 1(1^2) 和 9(3^2)

而且我们要定义 dp[0] = 1 也就是 目标是 0 的时候 有一个方案（这个方案就是 不选任何数）

回答上面的问题：光有这些数还不够，得想办法统计“哪些组合能加起来等于 n”。

这时候就该 动态规划 出场了，它就像一个记账本，帮我们一笔一笔记下 每种可能的和 有多少种凑法?

先给这个记账本下个定义 dp[j]

我要明确它是干嘛的：dp[]是一个数组，dp[j] = x 表示凑成和为 j 的方案有 x 种

比如 dp[5] = 2 表示 在当前的这些数中 能凑成 5 的方案 有 2 种

初始化：为什么偏偏是 dp [0] = 1？

之前提到dp[0] = 1，现在再细想：和为 0 的情况，只有“一个数都不选”这一种可能，所以方案数是 1。这就像记账本的“初始资金”，后面所有的方案数，其实都是从这个“1”慢慢衍生出来的。

如果 dp[0] 是 0，那后面所有计算都会是 0（因为每次更新都依赖 dp[j - val]，而最初的dp[j - val] 可能就是从 dp[0] 推来的），所以这个初始化是整个逻辑的“根基”。

处理每个侯选数，怎么更新这个“记账本”？

现在，我们进入上面定义的循环中，每一次循环我们都得到一个候选数，它一定满足在一个范围 [1,n] 之间 我们已经通过条件约束过了。

那么我们怎么来知道凑成当前候选数 有多少种方案呢？也就是下面的问题：

接下来就要思考：当新加入 val 这个数时，怎么更新 dp 里的记录？

具体问题还是要用例子来理解。

比如现在要处理 val = 4（2^2），我们已经初始化 dp[0] =1 , 而且 dp[1] =1（用 1 可以凑出 1），当前侯选数 4，那些和的方案数会改变？

我们要执行，从 1 到 n 递增，在内部 每次循环 从 n 到 val 递减，递减是为了保证每个数字都只用一次

• 能凑出和为 4 的方案：可以直接选 4 本身（4=4）所以 dp[4] 应该加上 凑出 dp[4-4]的方案数，也就是 dp[0] =1, 所以 dp[4] 从 0 变 1
• 同理，和为 6 时，可以是 4 +2 , 但目前我们还没处理过能凑出 2 的数，现在只有 1 和 4 所以 dp[6]暂时不变

这样的话，每次处理一个新的 val（外层循环 i 经 i^x 得到）其实是在问：如果我选了 val，能帮之前的哪些和“升级”成更大的“和”，这里升级的根据就是：j 的方案数 = 原来的方案数(不选 val 时) + 凑出 j -val（选 val 时），本质上是做方案数的累加。

关键的细节：为何必须从后往前 更新？

试想一下，如果我们按照习惯 从前往后遍历（从 val 到 n）那就是，先算小的 j =4, 再算大的 j =5，，这样会出问题。比如 当先处理了 val =1，也就是 dp[1] = dp[0] + dp[1] 是 1 方案，再算j=2：dp[2] += dp[1]→dp[2] = 1（这其实是 1 +1 但由于题目要求必须是互不相同的数相加，显然违反了规则）

原来，顺着遍历会导致使得同一个 val 被反复使用，因为算 j 时，j-val 可能已经被更新过了，我们算 j，其实就是用已有的方案加上当前的一个选择，而非正序的（会累加已有的方案 导致重复数字的使用）会违反题目的规定 导致某些方案很多

让内部的遍历过程更清晰

初始状态

dp数组初始化：dp = [1, 0, 0, 0, 0, 0]（dp[0]=1，其余为 0），MOD=1e9+7。

一、倒序遍历（正确逻辑）

内层循环为  for (j = n; j >= val; j--)

步骤 1：处理val=1（i=1，1^1=1）

• 遍历j=5 → 1，更新dp[j] += dp[j-1]：
  • j=5：dp[5] += dp[4] → 0 + 0 = 0
  • j=4：dp[4] += dp[3] → 0 + 0 = 0
  • j=3：dp[3] += dp[2] → 0 + 0 = 0
  • j=2：dp[2] += dp[1] → 0 + 0 = 0
  • j=1：dp[1] += dp[0] → 0 + 1 = 1
• 此时dp = [1, 1, 0, 0, 0, 0]

步骤 2：处理val=2（i=2，2^1=2）

• 遍历j=5 → 2，更新dp[j] += dp[j-2]：
  • j=5：dp[5] += dp[3] → 0 + 0 = 0
  • j=4：dp[4] += dp[2] → 0 + 0 = 0
  • j=3：dp[3] += dp[1] → 0 + 1 = 1（方案：1+2）
  • j=2：dp[2] += dp[0] → 0 + 1 = 1（方案：2）
• 此时dp = [1, 1, 1, 1, 0, 0]

步骤 3：处理val=3（i=3，3^1=3）

• 遍历j=5 → 3，更新dp[j] += dp[j-3]：
  • j=5：dp[5] += dp[2] → 0 + 1 = 1（方案：2+3）
  • j=4：dp[4] += dp[1] → 0 + 1 = 1（方案：1+3）
  • j=3：dp[3] += dp[0] → 1 + 1 = 2（方案：3 或 1+2）
• 此时dp = [1, 1, 1, 2, 1, 1]

步骤 4：处理val=4（i=4，4^1=4）

• 遍历j=5 → 4，更新dp[j] += dp[j-4]：
  • j=5：dp[5] += dp[1] → 1 + 1 = 2（新增方案：1+4）
  • j=4：dp[4] += dp[0] → 1 + 1 = 2（新增方案：4）
• 此时dp = [1, 1, 1, 2, 2, 2]

步骤 5：处理val=5（i=5，5^1=5）

• 遍历j=5 → 5，更新dp[j] += dp[j-5]：
  • j=5：dp[5] += dp[0] → 2 + 1 = 3（新增方案：5）
• 最终dp = [1, 1, 1, 2, 2, 3]

倒序结果：dp[5] = 3，对应正确方案：
2+3、1+4、5（共 3 种，均为互不相同的数）

此时 我们梳理一下过程：

1. 先圈定候选数：只留 i^x ≤ n 的val，排除不可能参与的数；
2. 定义dp[j]：记录“用已处理的数凑出和为 j 的方案数”；这是动态规划的一般步骤
3. 初始化dp[0] = 1：作为所有方案的起点
4. 逐个处理候选数：对每个 val，倒着遍历 j，用dp[j] += dp[j - val] 更新方案数（保证每个数只被用一次）；
5. 最终 dp[n] 就是答案：所有能凑出 n 的方案总和。

这样一来，从“枚举候选数”到“用动态规划统计方案”整个流程就算是清晰了

一刷，体会了动态规划的使用，作为初学者震撼着 也意识到 学习的路还很漫长。。。