동적 프로그래밍1 동적 프로그래밍 (DP) 해결 방법 동적 프로그래밍 (DP) 해결 방법 Step 1 : n이 가장 작을 때부터 하나하나 그려가보면서 규칙성을 찾는다 Step 2 : 규칙성이 보이기 시작하면 일반화하고, 점화식을 구한다. Step 3 : 탑다운 or 바텀업 중 좀 더 편한 방법으로 구현 (물론 연습할 때는 둘 다 해보기) 탑다운의 필수 요구사항, 바텀업의 필수 요구사항 꼭 숙지하기 탑 다운 필수요구사항 1. 값이 한없이 작아지는 것을 방지하기 위한 탈출조건 (n이 0이거나 1 정도에서 return 하고 끊는 조건이 필요) 2. memoization (시간 초과 방지) 3. 과거의 상태값을 불러올 때는 인덱스를 이용한 배열 직접 접근보다는 재귀함수를 이용한다. Example) dp[n-1] (X) => solve(n-1) (O) 바텀 업 필수.. 2022. 2. 6. 이전 1 다음
