동적계획법

프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 방법

• 이전에 구한 값을 기반으로 규칙성을 파악하여 다음 값을 구하는 것
• 하위 문제의 최적해를 적절히 사용하여 상위 문제를 해결
• 구현은 분할 정복 알고리즘과 유사
  • 주어진 문제를 부분 문제로 나누어 각 부분 문제의 답을 계산
  • 부문 문제들을 나누는데에 있어서 분할 후 주어진 부분문제의 정답을 한 번만 계산하고 저장해 두고 추후 해당 부분 문제에 대한 해답을 확인할 때 저장되어 있는 값을 확인

예시) 최적 분 문제 구조, 피보나치 수열....

---

피보나치 수열

첫째 항과 둘째 항이 1의 값을 가지고, 그 뒤의 모든 항은 바로 앞 두 항의 합으로 구성된 수열

소스

작성 언어: java

public static int[] fib;
public static int result = 0;

public static int FibonacciNumber(int A){
    // A번째 수 확인
    fib = new int[A];
    
    int result = calc(A-1)
    
    return result;
}

public static int calc(int A){
    if(A < 2){
        return fib[A] = 1;
    }
    if(fib[A] != 0){
        return fib[A];
    }
    else{
        return fib[A] = calc(A-1) + calc(A-2);
    }
} 

---

참고

https://namu.wiki/w/%EB%8F%99%EC%A0%81%20%EA%B3%84%ED%9A%8D%EB%B2%95#toc
https://sskl660.tistory.com/87