矩阵最长递增路径两种DFS解法的时间复杂度疑问

1. 带记忆化DFS的O(mn)时间复杂度解释 #

• 记忆化的核心是每个单元格的最长递增路径长度只会被计算一次：首次计算某个单元格时，会递归处理其四个方向的合法邻居（值更大的单元格），计算完成后将结果存入缓存数组；后续任何时候再访问该单元格，直接读取缓存值，耗时O(1)。
• 外层循环虽然遍历所有mn个单元格，但每个单元格的递归逻辑仅会真正执行一次。比如当单元格A递归到单元格B时，会触发B的首次计算；后续若其他单元格C再递归到B，直接用缓存的B的结果，不会重复递归。
• 总共有mn个单元格，每个仅被计算一次，每次计算的操作（检查方向、更新缓存）都是O(1)级别，因此总时间复杂度为O(mn)，而非你担心的O((mn)²)——后者是无记忆化时的最坏情况，记忆化彻底避免了重复计算。

2. 无记忆化DFS的O(2^(m+n))时间复杂度解释 #

• 首先明确：递增路径是严格递增的，路径中不会出现重复单元格（无法回头走到值更小的单元格），因此每个步骤的有效选择远少于4个。
• 官方给出的复杂度是基于最坏情况的矩阵结构：比如一个严格递增的网格，每个单元格仅能向两个方向延伸路径（例如只能向右或向下，因为左边和上边的值更小，不符合递增要求）。
• 这种场景下，路径的增长方式等价于网格中从起点到终点仅允许右/下移动的路径数，其数量为组合数C(m+n-2, m-1)，而该组合数的上限是O(2^{(m+n))（因为2}(m+n)是所有二进制选择的总数，组合数远小于这个值，因此用它作为时间复杂度的上界）。
• 你之前误以为每个单元格有4种选择，忽略了严格递增的限制——它直接排除了向值更小的方向移动的可能，因此实际每个步骤的有效选择最多为2个，时间复杂度的底数是2而非4，最终上界为O(2^(m+n))。

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