12-16-DP¶
Dynamic Programming¶
여러 개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘
점화식을 찾아낸 후 점화식의 항을 밑에서부터 차례로 구해나가서 답을 알아내는 형태의 알고리즘
풀이 과정¶
예) 1로 만들기
- 테이블 정의하기
- dp[i] = i를 1로 만들기 위해 필요한 연산 사용 횟수의 최솟값
- 점화식 찾기
- dp[k] = ?
- dp[k/3] + 1, dp[k/2] + 1, dp[k-1] + 1 중 최솟값
- 초기값 정하기
- dp[1] = 0