알고리즘 동적계획법

알고리즘 동적계획법

2 .동적계획법 - (이항계수구하기 / 플로이드 알고리즘 / 연쇄행렬곱셈)

동적계획법 알고리즘 개발 절차

1) 재귀 관계식 정립

2) 상향식 방법으로 문제를 해결(앞에서 구한 데이터로 다음문제 해결) -자료구조 배열사용

작은 문제처리 ->다음문제해결

최적의 해를 구하는 기법중 하나임.

어떤 솔루션의 부분집합도 최적의 솔루션이다 ( 최적의 원칙 성립)

플로이드 알고리즘 ( 최단경로 ) 시간복잡도 : O(n^3)