[LeetCode] 62. Unique Paths

전형적인 DP 문제의 입문.

Memoization을 위한 dp_map을 만들어 놓고 이미 방문한 경로에서 계산 된 Path 갯수를 저장해서 사용한다.

 

class Solution {
    int dest_x, dest_y;
    int dp_map[100][100];
    
public:
    
    Solution () : dest_x (0), dest_y (0) {
        for( int i = 0; i < 100; i++)
            for( int j = 0; j < 100; j++)
                dp_map[i][j] = -1;
    }
        
    int dfs ( int y, int x )
    {
        if ( y == dest_y - 1 && x == dest_x - 1 )
            return 1;
        
        int rr = 0;
        int rd = 0;
        
        // move right
        if ( x + 1 < dest_x )
        {
            if ( dp_map[y][x+1] == -1 )
            {
                rr = dfs( y, x + 1 );
                dp_map[y][x+1] = rr;
            }
            else 
                rr = dp_map[y][x+1];
            
        }
        
        // move down
        if ( y + 1 < dest_y )
        {
            if ( dp_map[y+1][x] == -1 )
            {
                rd = dfs( y + 1, x );
                dp_map[y+1][x] = rd;
            }
            else
                rd = dp_map[y+1][x];
        }
            
        
        return rr + rd;
    }
    
    int uniquePaths(int m, int n)
    {
        dest_x = n;
        dest_y = m;
        
        
        return dfs( 0, 0 );
    }
};