Cộng đồng Hỏi & Đáp của Inflearn
câu hỏi đã được viết
[Unique Paths] 완전탐색 / DP (후반부)
Đã giải quyết
Viết
·
94
0
[Unique Paths] 완전탐색 / DP (후반부) 강의에서 13분에서 질문있습니다. 첫 번째 행과 첫 번째 열이 모두 왜 1인가요?
만약 방향을 바꾸기 전까지 1이라고 친다면, 아래 그림 처럼 도착지에서 최대 방법이 28이 아니라 8이 되어야 하는거 아닌가요? 왜냐면 방향은 오른쪽 아래로만 이동이 가능하다고 해서 올라가거나 왼쪽은 이동이 불가능하잖아요.
Câu trả lời 1
0
안녕하세요. zzzzz님.
1. 첫 번째 행의 경우
시작점 (0,0)에서 첫 번째 행의 다른 칸 (0, j)으로 가려면 오른쪽으로만 이동할 수 있습니다.
오른쪽으로만 이동하는 경우, 선택의 여지가 없으므로 경로는 유일하게 1가지입니다.
따라서 dp[0][j] = 1 (모든 j)가 됩니다.
2. 첫 번째 열의 경우
마찬가지로, (0,0)에서 첫 번째 열의 다른 칸 (i, 0)으로 가려면 아래로만 이동할 수 있습니다.
아래로만 이동하면 역시 경로는 1가지입니다.
따라서 dp[i][0] = 1 (모든 i)가 됩니다.
3. 나머지 셀의 경우
임의의 셀 (i, j)에 도달하는 경로의 수는,
바로 위 (i-1, j)에서 오는 경로의 수와 왼쪽 (i, j-1)에서 오는 경로의 수의 합입니다.
즉, dp[i][j] = dp[i-1][j] + dp[i][j-1]가 됩니다.
이 문제의 핵심은 셀에 도달할 수 있는 모든 경우의 수를 구하는 것입니다. 직접 그림을 그리면서 생각해보시면 이해가 잘 되실 겁니다.
추가적인 질문이 있다면 편하게 질문 바랍니다.
감사합니다.