재귀 알고리즘의 두 가지 구현의 차이점은 무엇입니까?

Question

나는 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]; 
     } 
    } 
}; 

Answer 1

버전 1은 또 다시 같은 데이터를 계산하는 beacuse 느립니다. 나는 이것을 다른 문제에 대해 설명하려고 노력할 것이다. 그러나 당신은 피보나치 숫자를 알고 있다고 생각한다. 재귀 알고리즘에 따라 피보나치 수를 계산할 수 있습니다.

fib(n): 
if n == 0 then return 0 
if n == 1 then return 1 
return fib(n-1) + fib(n-1) 

실제로 계산하는 대상은 무엇입니까? fib (5)를 찾고 싶다면 fib (4)와 fib (3)을 계산하고, fib (4)를 계산하려면 fib (3)을 다시 계산해야합니다! 이미지를보고 완전히 이해하십시오.

동일한 상황이 코드에 있습니다. 이전에 계산 한 경우에도 uniquePaths (m, n)을 계산합니다. 이를 피하기 위해 두 번째 버전에서는 배열을 사용하여 계산 된 데이터를 저장하고 다시 계산할 필요가 없습니다. res[m][n]!=0