Dynamic programming(동적 프로그래밍): 부분 문제의 해를 결합하여 문제해결
->각 부분문제를 단 한번만 풀고 그 해를 저장
-Rod cutting(막대 자르기)
2. Dynamic programming: 다시 계산하지 않고 저장
Top-down
-> 둘 다 Θ(n^2)/ bottom-up:이중 중첩 루프/ top-down: 크기가 0,1,...n에 대한 하위문제를 한 번만 해결, 크기가 n인 부분문제를 풀기 위해 for루프 n번 반복
-Matrix-Chain Multiplication