[Quy Hoạch Động] - Tính dãy Fibonacci

Trong các kỹ thuật lập trình, quy hoạch động là một phương pháp giảm thời gian chạy của các thuật toán thể hiện các tính chất của các bài toán con gối nhau (overlapping subproblem) và cấu trúc con tối ưu (optimal substructure).
Dưới đây là ví dụ để so sánh tốc độ xử lý bài toán của phương pháp quy hoạch động (độ phức tạp là 0(n) ) so với phương pháp đệ quy.

Chương trình so sánh tốc độ của giải thuật quy hoạch động và đệ quy

/**
Fibonacy - Quy Hoach Dong va De Quy
**/

#include 
#include 

int fibonacyMemo(int n);
int fibonacyRev(int n);
int main(){
    int n = 1;
    while(n != 0){
            printf("input value n: ");
            scanf("%d",&n);
            printf("Fibonacy Meno: %d\n", fibonacyMemo(n));
             printf("Fibonacy Rev: %d\n\n", fibonacyRev(n));
    }
    
    getch();
    return 0;
}

int fibonacyMemo(int n){
    int pre = 1, next = 1;
    for(int i = 0; i < n-1; i++){
          int result = pre + next;
          pre = next;
          next = result;      
    }
    return next;
}

int fibonacyRev(int n){
    if(n ==0 || n== 1) return 1;
    else return fibonacyRev(n-1) + fibonacyRev(n-2);  
}