dp[i][j]dp[i][j]dp[i][j]를 "(0,0)(0,0)(0,0)에서 (i,j)(i, j)(i,j)까지 비용 합의 최솟값"이라 하면 위나 왼쪽 중 작은 쪽을 잇는다.
dp[i][j]=min(dp[i−1][j], dp[i][j−1])+cost[i][j]dp[i][j] = \min\bigl(dp[i-1][j], \; dp[i][j-1]\bigr) + \text{cost}[i][j]dp[i][j]=min(dp[i−1][j],dp[i][j−1])+cost[i][j]
입력: 3 3 1 3 1 1 5 1 4 2 1 출력: 7