격자에서 경로 개수 세기

격자의 왼쪽 위에서 시작해 오른쪽 아래로 가려고 합니다. 한 번에 오른쪽이나 아래쪽으로 이동할 수 있습니다. 서로 다른 경로가 몇 개나 있을까요?

각 칸은 위쪽 칸이나 왼쪽 칸에서 도달할 수 있습니다. 이러한 중복이 바로 이 문제가 DP 문제인 이유입니다.

dp[i][j]를 시작점에서 (i, j) 칸에 도달하는 방법의 수라고 하겠습니다. 상태를 명확하게 이름 붙이는 것이 문제 해결의 절반입니다.

위쪽이나 왼쪽에서만 도착할 수 있으므로, 개수는 두 값의 합입니다. 이것이 전체 표를 이끄는 전이입니다.

시작 칸에 도달하는 방법은 아무것도 하지 않는 한 가지뿐입니다. 따라서 다른 칸을 채우기 전에 dp[0][0]은 1입니다.

맨 위 행이나 맨 왼쪽 열의 칸에는 직선으로 이어지는 경로가 하나뿐입니다. 이 칸들은 이웃 하나가 격자 밖에 있으므로 개수는 항상 1입니다.

0으로 채운 m x n 표를 만드세요. 처음부터 크기를 정해 두면 인덱스를 깔끔하게 사용할 수 있고 예상치 못한 문제도 피할 수 있습니다.

행을 먼저, 열을 다음에 반복하면서 위에서 아래로, 왼쪽에서 오른쪽으로 진행하세요. 이 순서를 따르면 사용하기 전에 두 이웃 칸이 모두 준비됩니다.

표를 모두 채우면 경로의 개수는 마지막 칸에 있습니다. 정답은 오른쪽 아래 모서리인 dp[m-1][n-1]입니다.

각 행에는 바로 위 행만 필요하므로 한 행만 유지하면서 그 자리에서 갱신할 수 있습니다. 그러면 메모리를 O(n)으로 줄일 수 있습니다.

막힌 칸이 없다면 정답은 전체 이동 중 아래쪽으로 이동할 횟수를 고르는 이항 계수입니다. 장애물이 생기면 DP가 여전히 유리합니다.

열린 내부 칸의 dp[i][j]를 채우고 있습니다. 어떤 식이 올바를까요?

한 칸까지의 경로 수를 dp로 정의하고, dp[0][0]을 1로 설정한 다음 위쪽 칸과 왼쪽 칸을 더하세요. 모서리에 정답이 있습니다. 🧭