算法1

(暴力动态规划) $O(n^2)$

1. 设 $f(i, j)$ 表示使用 $i$ 个手机，测试塔高度为 $j$ 时的次数。$i$ 从 1 到 3，$j$ 从 0 到 $n$。
2. 初始时，$f(1, j) = j$，其余为正无穷。
3. 转移时，$f(i, j) = \min{f(i, j), \max(f(i - 1, k - 1), f(i, j - k)) + 1}$。表示当前的手机从 $k$ 处摔下时，碎和没碎的两种情况取最大值再加 1。找到价值最小的 $k$ 进行转移。
4. 最终答案为 $f(3, n)$。

时间复杂度

• 状态数为 $O(n)$，每个状态的转移时间为 $O(n)$，故总时间复杂度为 $O(n)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储状态。

C++ 代码

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>

using namespace std;

const int N = 10010;

int n;
int f[4][N];

int main() {
    scanf("%d", &n);
    memset(f, 0x3f, sizeof(f));

    for (int i = 0; i <= n; i++)
        f[1][i] = i;

    for (int i = 2; i <= 3; i++) {
        f[i][0] = 0;
        for (int j = 1; j <= n; j++)
            for (int k = 1; k <= j; k++)
                f[i][j] = min(f[i][j], max(f[i - 1][k - 1], f[i][j - k]) + 1);
    }

    printf("%d\n", f[3][n]);
    return 0;
}

算法2

(动态规划) $O(n)$

1. 算法 1 的时间复杂度过高，需要优化。
2. 考察最优决策点 $k$ 的选择。可以发现，对于某个 $j$，$f(i - 1, k - 1)$ 是单调递增的，$f(i, j - k)$ 是单调递减的，至此最优决策点可以通过二分法求出。
3. 进一步发现，最优决策点 $k$ 是随着 $j$ 而单调不减的。令 $c_j(k) = \max(f(i - 1, k), f(i, j - k))$，假设 $k_0$ 是当前 $j$ 的最优决策点，即 $c_j(1) \ge c_j(2) \ge \cdots \ge c_j(k_0) < c_j(k_0 + 1) \le c_j(k_0 + 1)$，即当 $k < k_0$，都有 $f(i - 1, j - k) \ge f(i, k - 1)$。
4. 对于 $j + 1$ 来说，反设其最优决策点 $k_1 = k_0 - t (t > 0)$，根据以上 $k < k_0$ 时的规则易得，$c_j(k_0 - t - 1) = c_{j+1}(k_0 - t) \le c_{j+1}(k_0) = c_j(k_0)$，与以上假设矛盾。故决策点必定不会小于 $k_0$。

时间复杂度

• 状态数为 $O(n)$，转移时间均摊为常数，故总时间复杂度为 $O(n)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储状态。

C++ 代码

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>

using namespace std;

const int N = 10010;

int n;
int f[4][N];

int main() {
    scanf("%d", &n);
    memset(f, 0x3f, sizeof(f));

    for (int i = 0; i <= n; i++)
        f[1][i] = i;

    for (int i = 2; i <= 3; i++) {
        f[i][0] = 0;
        int k = 1;
        for (int j = 1; j <= n; j++) {
            while (k < j && max(f[i - 1][k - 1], f[i][j - k]) >= max(f[i - 1][k], f[i][j - k - 1]))
                k++;
            f[i][j] = min(f[i][j], max(f[i - 1][k - 1], f[i][j - k]) + 1);
        }
    }

    printf("%d\n", f[3][n]);
    return 0;
}

算法3

(数学，递推) $O(\log n)$

1. 设 $f(i, j)$ 表示摔 $i$ 次，在拥有 $j$ 个手机的情况下，能达到的最大测试高度。
2. 初始时，$f(1, 0) = 0, f(1, j) = 1$。
3. 转移时，$f(i, j) = f(i - 1, j - 1) + f(i - 1, j) + 1$。前者为第 $j$ 的手机摔碎的情况下的最大测试高度，在此基础上，后者为没有摔碎的情况下，继续追加的最大测试高度。通俗的理解，即第 $i$ 次实验如果高度为 $f(i - 1, j - 1) + f(i - 1, j) + 1$ 时，在 $f(i - 1, j - 1)$ 这个位置测试摔下。
4. 求出 $f(i, 3) \ge n$ 的最小的 $i$。
5. 这里，状态的第一维可以省略，更新时只需要倒序更新即可。

时间复杂度

• 最多进行 $O(\log n)$ 轮更新，每轮更新仅需要常数的时间，故时间复杂度为 $O(\log n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>

using namespace std;

const int N = 10010;

int n;
int f[4];

int main() {
    scanf("%d", &n);
    f[0] = 0;
    for (int i = 1; i <= 3; i++)
        f[i] = 1;

    int ans = 1;
    while (f[3] < n) {
        for (int i = 3; i >= 1; i--)
            f[i] = f[i] + f[i - 1] + 1;
        ans++;
    }

    printf("%d\n", ans);
    return 0;
}

参考

LeetCode 887 题解