递归algorihtm的这两种实现有什么区别?

我正在处理leetcode问题。

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

所以我首先尝试了这个实现,得到了一个“超越运行时”(我忘记了确切的术语,但它意味着实现很慢)。所以我把它改为版本2,它使用数组来保存结果。老实说,我不知道递归在内部是如何工作的,也不知道为什么这两种实现具有不同的效率。

版本1(慢速):

class Solution {
   // int res[101][101]={{0}};
public:
    int uniquePaths(int m, int n) {
        if (m==1 || n==1) return 1;
        else{ 
            return uniquePaths(m-1,n) + uniquePaths(m,n-1);
        }
    }
};

版本2(更快):

class Solution {
    int res[101][101]={{0}};
public:
    int uniquePaths(int m, int n) {
        if (m==1 || n==1) return 1;
        else{ 
            if (res[m-1][n]==0) res[m-1][n] = uniquePaths(m-1,n);
            if (res[m][n-1]==0) res[m][n-1] = uniquePaths(m,n-1);
            return res[m-1][n] + res[m][n-1];
        }
    }
};