Loading... > https://leetcode.cn/problems/minimum-number-of-days-to-eat-n-oranges/description/?envType=daily-question&envId=2024-05-02 根据题目很容易想到递推式： $$ \begin{equation} f(i) = \begin{cases} 1 &\mbox{i = 1} \\ min{f(i - 1), f(i / 2), f(i / 3)} &\mbox{i 为 6 的倍数} \\ min{f(i - 1), f(i / 3)} &\mbox{i 为 3 的倍数} \\ min{f(i - 1), f(i / 2)} &\mbox{i 为 2 的倍数} \\ f(i - 1) + 1 &\mbox{其他} \\ \end{cases} \end{equation} $$ 直接递推就可以得到答案。但此方法的时间复杂度为 $O(n)$ ，题目中 $n$ 最大值为 $2 \times 10^9$ ，显然会超时，所以需要一些优化。 ### 递归 为了获得最少的天数，每天应该吃掉尽可能多的橘子，因此应该优先选择将橘子数变成 1/3 或 1/2 的操作。对于不同的橘子数 $i$ 来说： - 想要将 $i$ 变成 $3$ 的倍数至少需要 $i \% 3$ 次减一操作，因此 $f(i) = 1 + i \% 3 + f(\lfloor i / 3 \rfloor)$ ； - 想要将 $i$ 变成 $2$ 的倍数至少需要 $i \% 2$ 次减一操作，因此 $f(i) = 1 + i \% 2 + f(\lfloor i / 2 \rfloor)$ ； - 最后一次操作一定是吃一个橘子，将 $i$ 由 $1$ 变成 $0$ ，因此 $f(1) = 1$ 。 因此可以写出代码如下： ```c++ class Solution { public: int minDays(int n) { if (n < 2) return n; return 1 + std::min((n % 2) + minDays(n / 2), (n % 3) + minDays(n / 3)); } }; ``` - 时间复杂度： > 这个时间复杂度超出我能力范围了，放上题解给的计算方法作为参考 > 这个递归的时间复杂度比较不好计算。设 $n$ 对应的时间复杂度为 $T(n)$ ，那么有递推式： $$ T(n) = T(\frac{n}{2}) + T(\frac{n}{3}) + O(1) $$ 设 $T(n) = n^t$ ，代入递推式可以得到： $$ O(n^t) = O((\frac{n}{2})^t) + O((\frac{n}{3})^t) + O(1) $$ 两边同时除以 $O(n^t)$ ，忽略 $O(1)$ 可得： $$ 1 = (\frac{1}{2})^t + (\frac{1}{3})^t $$ 解得 $t \approx 0.788$ ，因此递归的时间复杂度为 $O(n^{0.788})$ 。 - 空间复杂度：$O(1)$ 。 ### 记忆化搜索 使用递归可以通过所有样例，但这个时间复杂度还是较高，理论上会 TLE 。此时可以使用记忆化搜索存下计算过的答案，这样可以剪掉大部分不必要的分支： ```c++ class Solution { private: unordered_map<int, int> saved; public: int minDays(int n) { if (n < 2) return n; if (saved.count(n)) return saved[n]; return saved[n] = 1 + std::min((n % 2) + minDays(n / 2), (n % 3) + minDays(n / 3)); } }; ``` > 这个时间复杂度超出我能力范围了，放上题解给的计算方法作为参考 这里需要使用到一个结论： > 对于正整数 $n,x,y$，有： > > $$ > \lfloor \lfloor n/x \rfloor / y \rfloor = \lfloor n/(xy) \rfloor = \lfloor \lfloor n/y \rfloor / x \rfloor > $$ 读者可以自行尝试证明。实际上，只有所有满足 $i = \lfloor n / (2^x3^y) \rfloor$ 的 $f(i)$ 值才会被计算，如果不使用记忆化，会造成大量的重复计算。 > 例如 $f(n)$ 递归调用了 $f(\lfloor n/2 \rfloor)$ 和 $f(\lfloor n/3 \rfloor)$，前者递归调用了 $f(\lfloor n/4 \rfloor)$ 和 $f(\lfloor n/6 \rfloor)$，后者递归调用了 $f(\lfloor n/6 \rfloor)$ 和 $f(\lfloor n/9 \rfloor)$，这样 $f(\lfloor n/6 \rfloor)$ 实际上计算了两次。 在使用了记忆化之后，根据 $i = \lfloor n / (2^x3^y) \rfloor$ )⌋，有 $x \leq \lfloor \log_2 n \rfloor$ 以及 $y \leq \lfloor \log_3 n \rfloor$，因此我们可以估计出需要计算的 $f(i)$ 的个数不超过 $\lfloor \log_2 n \rfloor * \lfloor \log_3 n \rfloor = O(\log^2 n)$。因此： - 时间复杂度：$O(\log^2 n)$ 。 - 空间复杂度：$O(\log^2 n)$ ，即为需要存储的 $f(i)$ 的个数。 最后修改：2024 年 05 月 12 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏