[DP] 격자 경로의 수

문제

$R \times C$ 격자가 있다. 각 칸은 빈칸($0$) 또는 막힌 칸($1$)이다. 왼쪽 위 $(0, 0)$에서 출발해 오른쪽 또는 아래로만 한 칸씩 움직여 오른쪽 아래 $(R-1, C-1)$에 닿는 경로의 수를 구하라. 막힌 칸은 지날 수 없다. 답이 클 수 있으니 $1{,}000{,}000{,}007$로 나눈 나머지를 출력한다. 시작이나 도착 칸이 막혀 있으면 $0$이다.

접근

$dp[i][j]$를 "$(0,0)$에서 $(i, j)$까지 오는 경로의 수"라 하면 위와 왼쪽에서만 올 수 있다.

$dp[i][j] = dp[i-1][j] + dp[i][j-1]$

막힌 칸은 $dp = 0$으로 두고 건너뛴다.

입출력 예시

입력:
3 3
0 0 0
0 1 0
0 0 0
출력: 2