GESP 八级 · GESP 202312 C++ 八级 第 11 题

下面程序的时间复杂度为（ ）。

int record_choose[MAXN][MAXM];
int choose(int n, int m) {
    if (m == 0 || m == n)
        return 1;
    if (record_choose[n][m] == 0)
        record_choose[n][m] = choose(n - 1, m - 1) + choose(n - 1, m);
    return record_choose[n][m];
}

这题别被递归树吓住，核心在于数清楚记忆化数组里到底存了多少个有效状态。拿到题先想：递归只会访问哪些 (n,m) 组合？这些组合的总数是多少？每个组合只算一次，时间复杂度就是状态数。

最容易错选 A，因为看到递归就下意识想二叉树展开是 2^n，完全忽略了记忆化让每个状态只算一次。其次是 C，把 C(n,m) 这个组合数的「数值大小」当成了「计算次数」，混淆了概念。还有人会卡在对 m 的依赖上，觉得 m 小一点就快很多，但题目问的是最坏情况，得看 m 和 n-m 都接近 n/2 时状态总数最大，这时候才是 O(m*(n-m)) 的峰值。

考点：递归与记忆化｜时间复杂度分析｜组合数递推

1. 考纲定位

八级算法模块「递归与搜索」中的经典动态规划入门题。命题人在这里卡住的是绝大多数考生的递归树节点数直觉——他们看到回溯结构就下意识想 O(2^n)，却完全忽略了「记忆化」这个最关键的条件。