[DP] 격자 최소 경로합

문제

$R \times C$ 격자의 각 칸에 양의 정수 비용이 적혀 있다. 왼쪽 위 $(0, 0)$에서 출발해 오른쪽 또는 아래로만 움직여 오른쪽 아래 $(R-1, C-1)$에 닿을 때, 지나간 칸 비용의 합이 최소가 되도록 하라.

접근

$dp[i][j]$를 "$(0,0)$에서 $(i, j)$까지 비용 합의 최솟값"이라 하면 위나 왼쪽 중 작은 쪽을 잇는다.

$dp[i][j] = \min\bigl(dp[i-1][j], \; dp[i][j-1]\bigr) + \text{cost}[i][j]$

입출력 예시

입력:
3 3
1 3 1
1 5 1
4 2 1
출력: 7