"BackTrack" Practice

列出所有0~4的排列組合

#include <stdio.h>
#include <stdlib.h>
int* A;
int sol[5];
void backtrack(int n){
    if(n==5){
        for(int i=0;i<n;i++)printf("%d ",sol[i]);
        printf("\n");
        return ;
    }
    for(int i=0;i<5;i++){
        int ok=1;
        for(int j=0;j<n;j++){
            if(sol[j]==i)ok=0;
        }
        if(ok){
            sol[n]=i;
            backtrack(n+1);
        }
    }
}

int main(){
    backtrack(0);
    return 0;
}

DP

Thanks my buddy tought me in a easily-understand way.

1. 遞迴
2. 筆記本
3. 下到上

f(1) = 1
f(2) = 1
f(3) = 2 = f(2) + f(1)
f(4) = f(3) + f(2)
f(5) = f(4) + f(3) = f(3) + f(2) + f(3) = f(2) + f(1) + f(2) + f(2) + f(1)

...
f(n) = f(n-1) + f(n-2)



// return f(n)
// DP
// n <= 1000
int arr[1001];
Zero(arr);
arr[1] = 1; // f(1) = 1
arr[2] = 1; // f(2) = 1
int f(int n) {
        if(arr[n] != 0) return arr[n];
        else return arr[n]=(f(n-1) + f(n-2));
}    
     
f(4) + f(3)
f(3) + f(2) + f(3)
f(2) + f(1) + f(2) + f(3)
2 + f(2) + f(3) // arr[3] = 2

int f(int n) {
        if(n == 1 || n == 2) return 1;

        // n >= 3
        int n_1 = 1 /* f(2) = 1 */,
            n_2 = 1 /* f(1) = 1 */,
            n;

        for(int i = 3; i <= n; ++i) {
                n = n_1 + n_2;
                n_2 = n_1;
                n_1 = n;
        }

        return n;
}