다이나믹 프로그래밍

1. 다이나믹 프로그래밍

다이나믹 프로그래밍은 문제를 보고 규칙을 찾아 점화식을 세워 문제를 푸는 방법을 얘기하는 것 같다. 가장 기본적인 예시로는 피보나치 수열 문제가 있다. 다이나믹 프로그래밍을 푸는 방법은 2가지 방식이 있다.

1. 재귀형식의 탑다운 방식
2. 반복문의 바텀업 방식

저자는 재귀형식보단 반복문의 형태를 익혀서 푸는 것이 더 좋을 것이라고 했다.

예제들을 풀면서 느낀건 다이나믹 프로그래밍 문제는 점화식을 꼭 세울 줄 알아야 하는 것 같다. 문제는 점화식을 세우는 방법을 파악하는 것이 포인트. 문제를 많이 풀어봐야 할 것 같다.

그리고 아직 문제를 몇개 안풀어보았지만, 지금까진 형식이 딱 2가지인 것 같다.

1. 최소가 되는 같은 느낌의 문제는 원래 하던 recursive 느낌의 bottom-up으로
2. 뭔가 전체 경우의 수? 같은 느낌이면 타일 문제를 생각하자.