문제* 아래 문제의 recursive property를 제시하라. 양 또는 음의 정수 원소들로 구성된 n×n 행렬이 주어지고, 행렬의 좌상단에서 시작하여 우하단까지 이동한다. 이동 방법 (제약조건)- 오른쪽이나 아래쪽으로만 이동할 수 있다.- 왼쪽, 위쪽, 대각선 이동은 허용하지 않는다. 목표행렬의 좌상단에서 시작하여 우하단까지 이동하되, 방문한 칸에 있는 수들을 더한 값이 최소화되도록 한다. 불법 이동 예 유효한 이동의 예 문제풀이 방법 1. 초기화- dp[0][0] = matrix[0][0]: 시작점은 그대로 자신의 값으로 초기화 - 첫 행과 첫 열은 이전 값에 현재 칸의 값(matrix의 값)을 더하여 초기화 (for문) 2. 점화식 dp[i][j] = matrix[i][j] + min(dp[i..
[Dynamic Programming] 행렬 경로 문제
문제* 아래 문제의 recursive property를 제시하라. 양 또는 음의 정수 원소들로 구성된 n×n 행렬이 주어지고, 행렬의 좌상단에서 시작하여 우하단까지 이동한다. 이동 방법 (제약조건)- 오른쪽이나 아래쪽으로만 이동할 수 있다.- 왼쪽, 위쪽, 대각선 이동은 허용하지 않는다. 목표행렬의 좌상단에서 시작하여 우하단까지 이동하되, 방문한 칸에 있는 수들을 더한 값이 최소화되도록 한다. 불법 이동 예 유효한 이동의 예 문제풀이 방법 1. 초기화- dp[0][0] = matrix[0][0]: 시작점은 그대로 자신의 값으로 초기화 - 첫 행과 첫 열은 이전 값에 현재 칸의 값(matrix의 값)을 더하여 초기화 (for문) 2. 점화식 dp[i][j] = matrix[i][j] + min(dp[i..
2024.06.17