求解MxN网格仅右移下移路径数的两种算法时空复杂度推导疑问

空间复杂度 #

你的猜想正确，为 O(m+n)。
严谨证明：递归调用过程中每一步只会将m减1或n减1，从初始值(m,n)递归到边界条件（m=1或n=1）的最长调用路径，就是单向递减其中一个维度再递减另一个维度，总层数为 (m-1)+(n-1) = m+n-2，没有额外的堆内存开销，所以空间复杂度由调用栈深度决定，为O(m+n)。

时间复杂度 #

为 O(2^(m+n))，属于指数级复杂度。
推导：该递归的解本质是组合数 C(m+n-2, m-1)（总共有m+n-2步移动，选m-1步向下剩余向右即可）。递归树的总节点数等于所有子问题的调用次数，求和后总调用次数等于 C(m+n, m) - 1，根据斯特林公式，组合数 C(m+n, m) 的上界为 2^(m+n)，因此时间复杂度为 O(2^(m+n))，确实随m+n的和呈指数增长。

时间复杂度 #

你的猜想正确，为 O(mn)。
推导：记忆化优化的核心是每个不同的(a,b)子问题只会被计算一次，a的取值范围为1_{m，b的取值范围为1}n，最多有mn个不同的子问题，每个子问题的计算仅涉及O(1)的查表、加法和存储操作，因此总时间复杂度为O(m*n)。你测试200×200得到19900个键，是因为你额外做了(m,n)和(n,m)的对称等价优化，正方形场景下实际存储量为 (m-1)m/2 = 199200/2=19900，和测试结果完全吻合，对称优化仅降低了常数系数，不影响大O复杂度等级。

空间复杂度 #

为 O(mn)*。
推导：空间开销由两部分组成：调用栈深度依旧是O(m+n)，记忆化存储的哈希表大小为O(mn)，取两者的最大值，因此整体空间复杂度为O(mn)。

内容的提问来源于stack exchange，提问作者hdw3