❌

普通视图

发现新文章，点击刷新页面。
今天 — 2025年8月14日LeetCode 每日一题题解

每日一题-判断一个数字是否可以表示成三的幂的和🟡

✇LeetCode 每日一题题解
2025年8月14日 00:00

给你一个整数 n ，如果你可以将 n 表示成若干个不同的三的幂之和，请你返回 true ，否则请返回 false 。

对于一个整数 y ，如果存在整数 x 满足 y == 3x ，我们称这个整数 y 是三的幂。

 

示例 1：

输入：n = 12
输出：true
解释：12 = 31 + 32

示例 2：

输入：n = 91
输出：true
解释：91 = 30 + 32 + 34

示例 3：

输入：n = 21
输出：false

 

提示：

  • 1 <= n <= 107

【爪哇缪斯】图解LeetCode

✇LeetCode 每日一题题解
作者 muse-77
2022年12月9日 09:01

解题思路

根据题目表述，我们要判断n是否满足三的幂之和，其实关于这道题，如果我们将三的幂之和改变为二的幂之和，就清晰多了。因为我们常用的二进制转成十进制，就是采用二的幂之和来计算获得了。那么，同理，我们采用三进制计算的方式，就可以获得这道题的答案了。

也就是说，我们通过对n进行除3取余操作，如果获得0或1，则表示满足三进制，依次类推，直到除完为止。如果在除3取余过程中，不满足0或者1，则直接返回false。具体逻辑，请参照下图所示：

image.png

代码实现

###java

class Solution {
    public boolean checkPowersOfThree(int n) {
        while (n != 0) {
            if (n % 3 == 0 || n % 3 == 1) n = n / 3; // 满足三进制
            else return false; // 不满足三进制，返回false
        }
        return true;
    }
}

image.png

今天的文章内容就这些了：

写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。

更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享，每天更新」

三进制

✇LeetCode 每日一题题解
作者 himymBen
2022年12月9日 07:31

Problem: 1780. 判断一个数字是否可以表示成三的幂的和

[TOC]

思路

一个数可以表示为不同的3的幂次的和，那么它的三进制每一位只能是1或0

解题方法

按三进制转换，确保三进制任意位中没有2

复杂度

  • 时间复杂度:

$O(log_{3}n)$

  • 空间复杂度:

$O(1)$

Code

###Python3


class Solution:
    def checkPowersOfThree(self, n: int) -> bool:
        while n:
            if n % 3 == 2:
                return False
            n //= 3
        return True

###Go

func checkPowersOfThree(n int) bool {
    for ; n > 0; n /= 3 {
        if n % 3 == 2 {
            return false
        }
    }
    return true
}

判断一个数字是否可以表示成三的幂的和

✇LeetCode 每日一题题解
作者 LeetCode-Solution
2022年12月8日 09:59

方法一：进制转换

思路与算法

我们可以将 $n$ 转换成 $3$ 进制。如果 $n$ 的 $3$ 进制表示中每一位均不为 $2$，那么答案为 $\text{True}$，否则为 $\text{False}$。

例如当 $n=12$ 时，$12 = (110)_3$，满足要求；当 $n=21$ 时，$21 = (210)_3$，不满足要求。

代码

###C++

class Solution {
public:
    bool checkPowersOfThree(int n) {
        while (n) {
            if (n % 3 == 2) {
                return false;
            }
            n /= 3;
        }
        return true;
    }
};

###Java

class Solution {
    public boolean checkPowersOfThree(int n) {
        while (n != 0) {
            if (n % 3 == 2) {
                return false;
            }
            n /= 3;
        }
        return true;
    }
}

###C#

public class Solution {
    public bool CheckPowersOfThree(int n) {
        while (n != 0) {
            if (n % 3 == 2) {
                return false;
            }
            n /= 3;
        }
        return true;
    }
}

###Python

class Solution:
    def checkPowersOfThree(self, n: int) -> bool:
        while n > 0:
            if n % 3 == 2:
                return False
            n //= 3
        return True

###C

bool checkPowersOfThree(int n) {
    while (n) {
        if (n % 3 == 2) {
            return false;
        }
        n /= 3;
    }
    return true;
}

###JavaScript

var checkPowersOfThree = function(n) {
    while (n !== 0) {
        if (n % 3 === 2) {
            return false;
        }
        n = Math.floor(n / 3);
    }
    return true;
};

###go

func checkPowersOfThree(n int) bool {
    for ; n > 0; n /= 3 {
        if n%3 == 2 {
            return false
        }
    }
    return true
}

复杂度分析

  • 时间复杂度：$O(\log n)$，即为进制转换需要的时间。

  • 空间复杂度：$O(1)$。

昨天 — 2025年8月13日LeetCode 每日一题题解

每日一题-3 的幂🟢

✇LeetCode 每日一题题解
2025年8月13日 00:00

给定一个整数，写一个函数来判断它是否是 3 的幂次方。如果是，返回 true ；否则，返回 false 。

整数 n 是 3 的幂次方需满足：存在整数 x 使得 n == 3x

 

示例 1：

输入：n = 27
输出：true

示例 2：

输入：n = 0
输出：false

示例 3：

输入：n = 9
输出：true

示例 4：

输入：n = 45
输出：false

 

提示：

  • -231 <= n <= 231 - 1

 

进阶：你能不使用循环或者递归来完成本题吗？

O(1) 数学做法，一行搞定（Python/Java/C++/C/Go/JS/Rust）

✇LeetCode 每日一题题解
作者 endlesscheng
2024年11月2日 14:20

$3$ 的幂一定大于 $0$。如果 $n\le 0$，那么 $n$ 不是 $3$ 的幂。下文假定 $n>0$。

在本题的数据范围下，最大的 $3$ 的幂是 $3^{19} = 1162261467$。

怎么算的？比如可以写个循环，找最大的满足 $3^i\le 2^{31}-1$ 的整数 $i$。

  • 如果 $n$ 是 $3$ 的幂。由于任何 $3$ 的幂都是 $3^{19}$ 的因子，所以 $3^{19}\bmod n = 0$。或者说 $n$ 的某个倍数等于 $3^{19}$。
  • 如果 $n$ 不是 $3$ 的幂。那么 $n$ 必然有不等于 $3$ 的质因子，所以 $n$ 的倍数不可能等于 $3^{19}$ 这个只含质因子 $3$ 的数，所以 $3^{19}\bmod n \ne 0$。

因此，在本题数据范围下，当且仅当 $n>0$ 且 $3^{19}\bmod n = 0$ 时，$n$ 是 $3$ 的幂。

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        return n > 0 and 1162261467 % n == 0

class Solution {
    public boolean isPowerOfThree(int n) {
        return n > 0 && 1162261467 % n == 0;
    }
}

class Solution {
public:
    bool isPowerOfThree(int n) {
        return n > 0 && 1162261467 % n == 0;
    }
};

bool isPowerOfThree(int n) {
    return n > 0 && 1162261467 % n == 0;
}

func isPowerOfThree(n int) bool {
    return n > 0 && 1162261467%n == 0
}

var isPowerOfThree = function(n) {
    return n > 0 && 1162261467 % n === 0;
};

impl Solution {
    pub fn is_power_of_three(n: i32) -> bool {
        n > 0 && 1162261467 % n == 0
    }
}

复杂度分析

  • 时间复杂度：$\mathcal{O}(1)$。
  • 空间复杂度：$\mathcal{O}(1)$。

分类题单

如何科学刷题？

  1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
  2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
  3. 单调栈（基础/矩形面积/贡献法/最小字典序）
  4. 网格图（DFS/BFS/综合应用）
  5. 位运算（基础/性质/拆位/试填/恒等式/思维）
  6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
  7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
  8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
  9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
  10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
  11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
  12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

【宫水三叶】一题三解 :「数学」&「倍数/约数」&「打表」

✇LeetCode 每日一题题解
作者 AC_OIer
2021年9月23日 08:50

数学

一个不能再朴素的做法是将 $n$ 对 $3$ 进行试除，直到 $n$ 不再与 $3$ 呈倍数关系，最后判断 $n$ 是否为 $3^0 = 1$ 即可。

代码：

###Java

class Solution {
    public boolean isPowerOfThree(int n) {
        if (n <= 0) return false;
        while (n % 3 == 0) n /= 3;
        return n == 1;
    }
}
  • 时间复杂度：$O(\log_{3}n)$
  • 空间复杂度：$O(1)$

倍数 & 约数

题目要求不能使用循环或递归来做，而传参 $n$ 的数据类型为 int，这引导我们首先分析出 int 范围内的最大 $3$ 次幂是多少，约为 $3^{19} = 1162261467$。

如果 $n$ 为 $3$ 的幂的话，那么必然满足 $n * 3^k = 1162261467$，即 $n$ 与 $1162261467$ 存在倍数关系。

因此，我们只需要判断 $n$ 是否为 $1162261467$ 的约数即可。

注意：这并不是快速判断 $x$ 的幂的通用做法，当且仅当 $x$ 为质数可用。

代码：

###Java

class Solution {
    public boolean isPowerOfThree(int n) {
        return n > 0 && 1162261467 % n == 0;
    }
}
  • 时间复杂度：$O(1)$
  • 空间复杂度：$O(1)$

打表

另外一个更容易想到的「不使用循环/递归」的做法是进行打表预处理。

使用 static 代码块，预处理出不超过 int 数据范围的所有 $3$ 的幂，这样我们在跑测试样例时，就不需要使用「循环/递归」来实现逻辑，可直接 $O(1)$ 查表返回。

代码：

###Java

class Solution {
    static Set<Integer> set = new HashSet<>();
    static {
        int cur = 1;
        set.add(cur);
        while (cur <= Integer.MAX_VALUE / 3) {
            cur *= 3;
            set.add(cur);
        }
    }
    public boolean isPowerOfThree(int n) {
        return n > 0 && set.contains(n);
    }
}
  • 时间复杂度：将打表逻辑交给 $OJ$ 执行的话，复杂度为 $O(\log_3{C})$，$C$ 固定为 $2147483647$；将打表逻辑放到本地执行，复杂度为 $O(1)$
  • 空间复杂度：$O(\log_3{n})$

其他「$x$ 的幂」问题

题目简单？不如来看「矩阵快速幂」三部曲 🍭🍭🍭：

题目 题解 难度 推荐指数
1137. 第 N 个泰波那契数 LeetCode 题解链接 简单 🤩🤩🤩🤩🤩
剑指 Offer 10- I. 斐波那契数列 LeetCode 题解链接 简单 🤩🤩🤩🤩🤩
552. 学生出勤记录 II LeetCode 题解链接 困难 🤩🤩🤩🤩

或是加练如下的「$x$ 的幂」问题 🍭🍭🍭：

题目 题解 难度 推荐指数
231. 2 的幂 LeetCode 题解链接 简单 🤩🤩🤩🤩
342. 4的幂 LeetCode 题解链接 简单 🤩🤩🤩🤩

最后

如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ ("▔□▔)/

也欢迎你 关注我（公主号后台回复「送书」即可参与长期看题解学算法送实体书活动）或 加入「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。

所有题解已经加入 刷题指南，欢迎 star 哦 ~

3的幂

✇LeetCode 每日一题题解
作者 LeetCode-Solution
2021年9月22日 22:39

方法一：试除法

思路与算法

我们不断地将 $n$ 除以 $3$，直到 $n=1$。如果此过程中 $n$ 无法被 $3$ 整除，就说明 $n$ 不是 $3$ 的幂。

本题中的 $n$ 可以为负数或 $0$，可以直接提前判断该情况并返回 $\text{False}$，也可以进行试除，因为负数或 $0$ 也无法通过多次除以 $3$ 得到 $1$。

代码

###C++

class Solution {
public:
    bool isPowerOfThree(int n) {
        while (n && n % 3 == 0) {
            n /= 3;
        }
        return n == 1;
    }
};

###Java

class Solution {
    public boolean isPowerOfThree(int n) {
        while (n != 0 && n % 3 == 0) {
            n /= 3;
        }
        return n == 1;
    }
}

###C#

public class Solution {
    public bool IsPowerOfThree(int n) {
        while (n != 0 && n % 3 == 0) {
            n /= 3;
        }
        return n == 1;
    }
}

###Python

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        while n and n % 3 == 0:
            n //= 3
        return n == 1

###JavaScript

var isPowerOfThree = function(n) {
    while (n !== 0 && n % 3 === 0) {
        n = Math.floor(n / 3);
    }
    return n === 1;
};

###go

func isPowerOfThree(n int) bool {
    for n > 0 && n%3 == 0 {
        n /= 3
    }
    return n == 1
}

复杂度分析

  • 时间复杂度：$O(\log n)$。当 $n$ 是 $3$ 的幂时，需要除以 $3$ 的次数为 $\log_3 n = O(\log n)$；当 $n$ 不是 $3$ 的幂时，需要除以 $3$ 的次数小于该值。

  • 空间复杂度：$O(1)$。

方法二：判断是否为最大 $3$ 的幂的约数

思路与算法

我们还可以使用一种较为取巧的做法。

在题目给定的 $32$ 位有符号整数的范围内，最大的 $3$ 的幂为 $3^{19} = 1162261467$。我们只需要判断 $n$ 是否是 $3^{19}$ 的约数即可。

与方法一不同的是，这里需要特殊判断 $n$ 是负数或 $0$ 的情况。

代码

###C++

class Solution {
public:
    bool isPowerOfThree(int n) {
        return n > 0 && 1162261467 % n == 0;
    }
};

###Java

class Solution {
    public boolean isPowerOfThree(int n) {
        return n > 0 && 1162261467 % n == 0;
    }
}

###C#

public class Solution {
    public bool IsPowerOfThree(int n) {
        return n > 0 && 1162261467 % n == 0;
    }
}

###Python

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        return n > 0 and 1162261467 % n == 0

###JavaScript

var isPowerOfThree = function(n) {
    return n > 0 && 1162261467 % n === 0;
};

###go

func isPowerOfThree(n int) bool {
    return n > 0 && 1162261467%n == 0
}

复杂度分析

  • 时间复杂度：$O(1)$。

  • 空间复杂度：$O(1)$。

昨天以前LeetCode 每日一题题解

每日一题-将一个数字表示成幂的和的方案数🟡

✇LeetCode 每日一题题解
2025年8月12日 00:00

给你两个 正 整数 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 次方之和的方案。

示例 2：

输入：n = 4, x = 1
输出：2
解释：我们可以将 n 按以下方案表示：
- n = 41 = 4 。
- n = 31 + 11 = 4 。

 

提示：

  • 1 <= n <= 300
  • 1 <= x <= 5

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

✇LeetCode 每日一题题解
作者 stormsunshine
2024年6月14日 21:39

解法

思路和算法

计算 $\textit{maxNum} = \lfloor \sqrt[x]{n} \rfloor$，则当 $n$ 表示成各不相同的正整数的 $x$ 次幂之和时，任何一个作为底数的正整数都不能超过 $\textit{maxNum}$。问题等价于计算从 $1^x$ 到 $\textit{maxNum}^x$ 的 $\textit{maxNum}$ 个正整数的 $x$ 次幂中选取一个或多个数字满足选取的数字之和等于 $n$ 的方案数。

该问题是 0-1 背包问题的变种，和传统 0-1 背包问题的区别在于，这道题要求选取的数字之和恰好等于 $n$。对于每个数字，选取的数字之和取决于之前选取的数字，因此可以使用动态规划计算选取的数字之和等于 $n$ 的方案数。

创建 $(\textit{maxNum} + 1) \times (n + 1)$ 的二维数组 $\textit{dp}$，其中 $\textit{dp}[i][j]$ 表示在前 $i$ 个数字中选取数字使数字之和等于 $j$ 的方案数。

当 $i = 0$ 时，没有任何数字，数字之和一定是 $0$，因此动态规划的边界情况是：当 $j = 0$ 时 $\textit{dp}[0][j] = 1$，当 $j > 0$ 时 $\textit{dp}[0][j] = 0$。

当 $i > 0$ 时，当前数字是 $i^x$，只有当 $j \ge i^x$ 时才能选取当前数字。分别考虑 $j < i^x$ 和 $j \ge i^x$ 的情况。

  • 如果 $j < i^x$，则不能选取当前数字，在前 $i$ 个数字中选取数字使数字之和等于 $j$ 等价于在前 $i - 1$ 个数字中选取数字使数字之和等于 $j$，因此方案数为 $\textit{dp}[i - 1][j]$。

  • 如果 $j \ge i^x$，则可以不选取或选取当前数字，根据两种情况计算方案数。

    • 如果不选取当前数字，则需要在前 $i - 1$ 个数字中选取数字使数字之和等于 $j$，方案数为 $\textit{dp}[i - 1][j]$。

    • 如果选取当前数字，则需要在前 $i - 1$ 个数字中选取数字使数字之和等于 $j - i^x$，加上选取的当前数字之后数字之和等于 $j$，因此方案数为 $\textit{dp}[i - 1][j - i^x]$。

因此动态规划的状态转移方程如下。

  • 如果 $j < i^x$，则 $\textit{dp}[i][j] = \textit{dp}[i - 1][j]$。

  • 如果 $j \ge i^x$，则 $\textit{dp}[i][j] = \textit{dp}[i - 1][j] + \textit{dp}[i - 1][j - i^x]$。

根据动态规划的状态转移方程，计算 $\textit{dp}[i][j]$ 的顺序为从小到大遍历每个 $i$。计算得到 $\textit{dp}[\textit{maxNum}][n]$ 即为将 $n$ 表示成各不相同的正整数的 $x$ 次幂之和的方案数。

上述做法的时间复杂度和空间复杂度都是 $O(\sqrt[x]{n} \times n)$。

实现方面可以优化空间，做法如下。

  1. 由于 $\textit{dp}[i][]$ 只取决于 $\textit{dp}[i - 1][]$，和更早的状态无关，因此可以使用滚动数组的思想，只保留前一个 $i$ 处的状态，将空间复杂度降到 $O(n)$。

  2. 优化空间时，如果从小到大遍历每个 $j$ 则对于每个遍历到的 $i$ 都需要新建一个临时数组。可以进一步优化空间，从大到小遍历每个 $j$，则不需要新建临时数组。

为了避免浮点数误差，计算 $\textit{maxNum}$ 时可以取 $\textit{maxNum} = \lfloor \sqrt[x]{n + 0.5} \rfloor$。

代码

下面的代码为不优化空间的实现。

###Java

class Solution {
    static final int MODULO = 1000000007;

    public int numberOfWays(int n, int x) {
        int maxNum = (int) Math.pow(n + 0.5, 1.0 / x);
        int[][] dp = new int[maxNum + 1][n + 1];
        dp[0][0] = 1;
        for (int i = 1; i <= maxNum; i++) {
            int power = (int) Math.pow(i, x);
            for (int j = 0; j <= n; j++) {
                if (j < power) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - power]) % MODULO;
                }
            }
        }
        return dp[maxNum][n];
    }
}

###C#

public class Solution {
    const int MODULO = 1000000007;

    public int NumberOfWays(int n, int x) {
        int maxNum = (int) Math.Pow(n + 0.5, 1.0 / x);
        int[][] dp = new int[maxNum + 1][];
        for (int i = 0; i <= maxNum; i++) {
            dp[i] = new int[n + 1];
        }
        dp[0][0] = 1;
        for (int i = 1; i <= maxNum; i++) {
            int power = (int) Math.Pow(i, x);
            for (int j = 0; j <= n; j++) {
                if (j < power) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - power]) % MODULO;
                }
            }
        }
        return dp[maxNum][n];
    }
}

下面的代码为优化空间的实现。

###Java

class Solution {
    static final int MODULO = 1000000007;

    public int numberOfWays(int n, int x) {
        int maxNum = (int) Math.pow(n + 0.5, 1.0 / x);
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for (int i = 1; i <= maxNum; i++) {
            int power = (int) Math.pow(i, x);
            for (int j = n; j >= power; j--) {
                dp[j] = (dp[j] + dp[j - power]) % MODULO;
            }
        }
        return dp[n];
    }
}

###C#

public class Solution {
    const int MODULO = 1000000007;

    public int NumberOfWays(int n, int x) {
        int maxNum = (int) Math.Pow(n + 0.5, 1.0 / x);
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for (int i = 1; i <= maxNum; i++) {
            int power = (int) Math.Pow(i, x);
            for (int j = n; j >= power; j--) {
                dp[j] = (dp[j] + dp[j - power]) % MODULO;
            }
        }
        return dp[n];
    }
}

复杂度分析

代码中使用了 $\texttt{Math.pow}$ 方法，该方法调用了本地方法 $\texttt{StrictMath.pow}$，因此其时间与空间复杂度取决于本地方法的实现，此处的复杂度分析将该方法的时间复杂度和空间复杂度视为 $O(1)$。

  • 时间复杂度：$O(\sqrt[x]{n} \times n)$，其中 $n$ 和 $x$ 是给定的正整数。状态数是 $O(\sqrt[x]{n} \times n)$，每个状态的计算时间是 $O(1)$，因此时间复杂度是 $O(\sqrt[x]{n} \times n)$。

  • 空间复杂度：$O(\sqrt[x]{n} \times n)$ 或 $O(n)$，其中 $n$ 和 $x$ 是给定的正整数。空间复杂度取决于实现方式，不优化空间的实现需要创建大小为 $(\lfloor \sqrt[x]{n} \rfloor + 1) \times (n + 1)$ 的二维数组因此空间复杂度是 $O(\sqrt[x]{n} \times n)$，优化空间的实现需要创建长度为 $n + 1$ 的一维数组因此空间复杂度是 $O(n)$。

0-1 背包模板题（Python/Java/C++/C/Go/JS/Rust）

✇LeetCode 每日一题题解
作者 endlesscheng
2023年7月23日 08:09

把 $n$ 看成背包容量，$1^x,2^x,3^x,\dots$ 看成物品，本题是恰好装满型 0-1 背包的方案数，做法同 494. 目标和，原理讲解见【基础算法精讲 18】，包含倒序循环的讲解。

代码实现时，由于最坏情况 $n=300$，$x=1$ 的答案没有超过 $64$ 位整数的最大值，可以在计算结束后再取模。

class Solution:
    def numberOfWays(self, n: int, x: int) -> int:
        f = [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):
                f[s] += f[s - v]
        return f[n] % 1_000_000_007

# 预处理所有答案
MX_N = 300
MX_X = 5
f = [[1] + [0] * MX_N for _ in range(MX_X + 1)]
for x in range(1, MX_X + 1):
    for i in count(1):
        v = i ** x
        if v > MX_N:
            break
        for s in range(MX_N, v - 1, -1):
            f[x][s] += f[x][s - v]

class Solution:
    def numberOfWays(self, n: int, x: int) -> int:
        return f[x][n] % 1_000_000_007

class Solution {
    int numberOfWays(int n, int x) {
        long[] f = new long[n + 1];
        f[0] = 1;
        // 本题数据范围小，Math.pow 的计算结果一定准确
        for (int i = 1; Math.pow(i, x) <= n; i++) {
            int v = (int) Math.pow(i, x);
            for (int s = n; s >= v; s--) {
                f[s] += f[s - v];
            }
        }
        return (int) (f[n] % 1_000_000_007);
    }
}

class Solution {
public:
    int numberOfWays(int n, int x) {
        vector<long long> f(n + 1);
        f[0] = 1;
        // 本题数据范围小，pow 的计算结果一定准确
        for (int i = 1; pow(i, x) <= n; i++) {
            int v = pow(i, x);
            for (int s = n; s >= v; s--) {
                f[s] += f[s - v];
            }
        }
        return f[n] % 1'000'000'007;
    }
};

#define MOD 1000000007

int numberOfWays(int n, int x) {
    long long* f = calloc(n + 1, sizeof(long long));
    f[0] = 1;

    // 本题数据范围小，pow 的计算结果一定准确
    for (int i = 1; pow(i, x) <= n; i++) {
        int v = pow(i, x);
        for (int s = n; s >= v; s--) {
            f[s] += f[s - v];
        }
    }

    int ans = f[n] % MOD;
    free(f);
    return ans;
}

func numberOfWays(n, x int) int {
f := make([]int, n+1)
f[0] = 1
for i := 1; pow(i, x) <= n; i++ {
v := pow(i, x)
for s := n; s >= v; s-- {
f[s] += f[s-v]
}
}
return f[n] % 1_000_000_007
}

// 本题数据范围小，math.Pow 的计算结果一定准确
func pow(i, x int) int {
return int(math.Pow(float64(i), float64(x)))
}

var numberOfWays = function(n, x) {
    const f = new Array(n + 1).fill(0);
    f[0] = 1;
    // 本题数据范围小，pow 的计算结果一定准确
    for (let i = 1; Math.pow(i, x) <= n; i++) {
        const v = Math.pow(i, x);
        for (let s = n; s >= v; s--) {
            f[s] += f[s - v];
        }
    }
    return f[n] % 1_000_000_007;
};

impl Solution {
    pub fn number_of_ways(n: i32, x: i32) -> i32 {
        let n = n as usize;
        let mut f = vec![0i64; n + 1];
        f[0] = 1;
        for i in 1usize.. {
            let v = i.pow(x as u32);
            if v > n {
                break;
            }
            for s in (v..=n).rev() {
                f[s] += f[s - v];
            }
        }
        (f[n] % 1_000_000_007) as _
    }
}

复杂度分析

  • 时间复杂度：$\mathcal{O}(n\sqrt[x]n)$。外层循环的循环次数为 $\mathcal{O}(\sqrt[x]n)$。
  • 空间复杂度：$\mathcal{O}(n)$。

注：也可以用快速幂计算 $\texttt{pow}$，原理见【图解】一张图秒懂快速幂。

专题训练

见下面动态规划题单的「§3.1 0-1 背包」。

分类题单

如何科学刷题？

  1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
  2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
  3. 单调栈（基础/矩形面积/贡献法/最小字典序）
  4. 网格图（DFS/BFS/综合应用）
  5. 位运算（基础/性质/拆位/试填/恒等式/思维）
  6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
  7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
  8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
  9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
  10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
  11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
  12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

三种方法解决：记忆化搜索，2维DP(背包），1维DP(背包）

✇LeetCode 每日一题题解
作者 desertear
2023年7月23日 07:51

请见下面代码中的注释：

###python

class Solution:
    # 方法一：记忆化搜索
    def numberOfWays(self, n: int, x: int) -> int:
        mod = 10 ** 9 + 7
        @cache
        # 函数dfs(num, target)的解释:
        # num:当前遍历到的数
        # target:期望组合成的数
        # dfs()的意义：找到以整数num开始的，能形成幂和的方案数
        # 以例题1:"输入：n = 10, x = 2" 为例，可以由下面步骤得来：
        # 1. 从整数1，2，3中依次寻找， 从1开始
        # 2-1. 如果到达1，如果选择了1，那方案数为dfs(0, 10 - 1 ** 2)，即dfs(0, 9)
        # 2-2. 如果到达1，但是没有选择1，那方案数为dfs(0, 10)，即到达0，目的仍然为10的方案数
        # 3. 所以到达1的方案数dfs(1, 10) = dfs(0, 10 - 1 ** 2) + dfs(0, 10)
        def dfs(num, target):
            # 如果target为0，说明已经组合成功，则返回1（种情况）
            if target == 0:
                return 1
            # 如果当前数的x幂已经超过target了，说明后面已经没必要进行下去（因为是正整数）
            if num ** x > target:
                return 0
            # 选择了当前的整数的方案数
            res = dfs(num+1, target- num ** x) % mod
            # 加上不选择当前的整数的方案数
            res = (res + dfs(num+1, target)) % mod
            return res
        # dfs(1, n)意思是从整数1开始找，目标是n的方案数
        return dfs(1, n)

    # 方法二：二维DP/背包问题，时间O(nlogn)，空间O(nlogn)
    def numberOfWays(self, n: int, x: int) -> int:
        mod = 10 ** 9 + 7
        # 此处用n+1的原因是防止精度丢失，比如n=64, x = 3，math.pow(64, 1/3) = 2.999999，会导致max_num = 2
        max_num = int(math.pow(n+1, 1/x))
        # DP[num][target]意义为：方案选到整数num时，能够组成幂和为target的方案数
        dp = [[0] * (n+1) for _ in range(max_num+1)]
        # 初始化：方案选为0时，幂和为0的方案数为1
        dp[0][0] = 1
        for num in range(1, max_num+1):
            for target in range(n+1):
                # 不选num数时
                dp[num][target] = dp[num-1][target]
                # 选num数时，需要保证target-num ** x >=0，能才选
                if target >= num ** x:
                    dp[num][target] = (dp[num][target] + dp[num-1][target-num ** x]) % mod
        return dp[max_num][n]


    # 方法三：优化后的一维DP/背包问题, 时间O(nlogn)，空间O(logn)
    def numberOfWays(self, n: int, x: int) -> int:
        mod = 10 ** 9 + 7
        max_num = int(math.pow(n+1, 1/x))
        dp = [0] * (n+1)
        dp[0] = 1
        for num in range(1, max_num+1):
            # 此处为倒序
            # 以上述二维dp的转移方程为例：dp[num][target] = dp[num-1][target] + dp[num][target-num**x]
            # 可以知道当前的状态dp[num][target]只与上一行有关，而且只与上一行的并且列数小于等于当前列的状态有关
            # 请大家画个矩阵出来，就可以容易的看出，只有使用倒序，在更新最新一行时，不会覆盖对后面有意义的上一行的数据
            for target in range(n, -1, -1):
                if target >= num ** x:
                    dp[target] = (dp[target] + dp[target - num ** x] ) % mod
        return dp[n]
❌
❌