Link to the solution

Link to the problem

1. 소개

꽤 직관적인 동적 프로그래밍을 사용하여 무차별 대입 솔루션을 알아낼 수 있었습니다. 하지만 내 솔루션에 메모이제이션을 구현하는 방법을 알 수 없었습니다. 문제의 토론 페이지에서 해결책과 설명 중 하나를 찾았고 여러분과 공유하고 싶습니다.

2. 문제 설명

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.

나의 이해

각 그리드에 대해 확인할 방향이 두 가지뿐이므로 전달된 행 및 열 인덱스가 범위를 벗어나거나 대상 그리드에 있을 때까지 재귀를 사용했습니다. 함수가 목적지에 도달하면 1을 반환하고 그렇지 않으면 0을 반환합니다.

함수의 끝에서 오른쪽 블록과 아래쪽 블록을 각각 검사하는 두 개의 재귀 호출의 합계를 반환합니다.

내 무차별 대입 솔루션⬇️ (솔루션은 결국 Leetcode에서 시간 제한 초과 오류를 얻습니다)

class Solution {
public:
    int uniquePaths(int m, int n) { 
        return findPaths(m,n,0,0);
    }

    int findPaths(int m, int n, int row, int col){

        // Checking out bound error
        if(row < 0 || col < 0 || row >= m || col >= n) return 0;

        // Checking if the function reached to the destination
        if(row == m-1 && col == n-1) return 1;

        // return the sum of paths
        return findPaths(m,n,row+1,col) + findPaths(m,n,row,col+1);
    }

};

3. 메모이제이션을 이용한 효율적인 솔루션

핵심 개념

첫째, 메모이제이션을 구현하는 목적을 상기하는 것이 좋습니다. 왜 우리는 이것을 하고 싶어할까요?

Wikipedia의 메모이제이션 정의:

In computing, memoization or memoisation is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.

따라서 우리의 목표는 중복 함수 호출을 방지하기 위해 이전 결과의 결과를 저장하는 것입니다. 그러나 메모이제이션을 구현하기 전에 알아야 할 한 가지 중요한 사항이 있습니다. 메모이제이션이 공간 복잡성을 희생하여 시간 복잡성을 높일 수 있을까요?

이 특정 문제에 대한 대답은 "예"입니다. 아래쪽과 오른쪽 지점을 스캔하는 동안 너무 많은 중복 함수 호출을 호출하고 있으며 프로그램이 더 무거운 테스트 사례를 통과하도록 이를 피하고 싶습니다. 메모화가 코드를 더 효율적으로 만드는 방법을 설명하는 다이어그램을 만들었습니다. Link to PDF


메모이제이션 다이어그램 (2022/07/09 by 권순범)

코드 구현

Link to the solution