为什么唯一路径问题的回溯解是O（2^max（m，n））？

Question

这是LeetCode的唯一路径问题https://leetcode.com/problems/unique-paths/.

m x n网格上有一个机器人。机器人最初位于左上角（即网格[0][0]）。机器人试图移动到右下角（即网格[m-1][n-1]）。机器人只能在任何时间点向下或向右移动。

给定两个整数m和n，返回机器人到达右下角可能的唯一路径数。

这是来自教程杯的回溯解决方案https://www.tutorialcup.com/leetcode-solutions/unique-paths-leetcode-solution.htm

import java.util.*;
import java.lang.*;
import java.io.*;
class Solution {
   public static int uniquePaths(int m, int n) {
       if(m == 1 || n == 1)
           return 1;
       return uniquePaths(m-1, n) + uniquePaths(m, n-1);
   }
   
   public static void main(String[] args){
     System.out.print(uniquePaths(2,2));
   }
}

wbesite中提到的最差时间复杂度为O（2^max（m，n））。在我看来这是不对的。

我认为有m*n的可能性，在每个递归步骤中减少一个。

T(mn) = T(mn-1) + T(mn-1)
     = 2 * T(mn-1)
     = 2^mn

所以最糟糕的时间复杂度是O（2^mn）。让我知道我的计算是否正确，或者我是否遗漏了什么

Answer 1

我认为有m*n的可能性，在每个递归步骤中减少一个。

不，它在每一步中减少n或m。所以：

T(mn) = T(m(n-1)) + T((m-1)n) + 1

这反映了您的递归调用：两个参数（传递给递归调用）的乘积表示剩余问题空间的大小。

为了计算时间复杂度，添加常数项很重要，因为函数的每次调用都代表工时/时间。

此外，使用这种符号，相同但来自不同网格大小的产品之间的区别消失了。应将两个维度分开：

T(m, n) = T(m, n-1) + T(m-1, n) + 1
T(m, 1) = 1
T(1, n) = 1

基本情况表示只剩下一列或一行，然后机器人只能在一个方向上移动——通过一条路径。