99클럽 코테 스터디 41일차 TIL < Unique Paths 2 >

오늘의 문제

 

 

You are given an m x n integer array grid. There is a robot 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.

An obstacle and space are marked as 1 or 0 respectively in grid. A path that the robot takes cannot include any square that is an obstacle.

Return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The testcases are generated so that the answer will be less than or equal to 2 * 109.ㅁ

 

학습 키워드

 

---

 
동적계획법

---

 
문제 풀이

1.

 

---

코드

 

class Solution {
    int[][] g;
    Integer[][] memo;
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        g=obstacleGrid;
        memo=new Integer[g.length][g[0].length];
        return f(0, 0);
    }
    private int f(int i, int j) {
        if(i==g.length || j==g[0].length || g[i][j]==1) return 0;
        if(i==g.length-1 && j==g[0].length-1) return 1;
        if(memo[i][j]!=null) return memo[i][j];
        return memo[i][j]=f(i+1,j)+f(i,j+1);
    }
}ㅁ

 

 
 
오늘의 회고