为什么这个唯一路径问题的回溯解是 O(2^max(m,n))？

Question

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

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

这是来自 tutorialcup 的回溯解决方案 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

I think there is m*n possibilities which is reduced by one in each recursive step.

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

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

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

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

此外，使用这种表示法，相同但来自不同网格大小的产品之间的区别就消失了。您应该将 2 个维度分开：

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

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

为什么这个唯一路径问题的回溯解是 O(2^max(m,n))？

Why this backtracking solution for Unique Path problem is O(2^max(m,n))?

java

algorithm

time-complexity

backtracking