보통DP

격자 경로의 수

m행 n열 격자가 있어요. 왼쪽 위 칸에서 시작해 오른쪽 또는 아래로만 한 칸씩 움직여 오른쪽 아래 칸까지 가려고 해요. 서로 다른 경로가 몇 개인지 반환해요.

어떤 칸에 도착하는 경로 수는 위 칸까지의 경로 수 + 왼쪽 칸까지의 경로 수예요. 맨 윗줄과 맨 왼쪽 줄은 한 가지 길뿐이니 1로 두고, 나머지를 왼쪽 위부터 채워 나가요.

예시

예시 1

입력: m = 3, n = 7
출력: 28

예시 2

입력: m = 3, n = 2
출력: 3
설명: 아래-아래-오른쪽, 아래-오른쪽-아래, 오른쪽-아래-아래 세 가지예요.

제한 사항

1 ≤ m, n ≤ 15

길이 n짜리 dp 배열을 1로 채우고, 두 번째 줄부터 각 칸을 dp[j] += dp[j - 1]로 갱신해요(dp[j]는 위 칸, dp[j-1]은 왼쪽 칸). m줄을 다 처리하면 dp[n-1]이 답이에요.

javascript
Copy code
function uniquePaths(m, n) {
  const dp = new Array(n).fill(1);
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[j] += dp[j - 1];
    }
  }
  return dp[n - 1];
}

이전 문제최장 증가 부분 수열

다음 문제0-1 배낭

예시 테스트만 실행 (Cmd/Ctrl+Enter)

숨김 테스트까지 채점 (Cmd/Ctrl+Shift+Enter)

에디터를 불러오고 있어요…

코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.