동적 계획법에서 필요로 되는

reference transparency 및 최적 부분 조건이 성립해야한다.

최적 부분 조건이 성립하도록 점화식을 만들어야한다.

Quantization (Need Improv.) 버전은 이부분을 고려하지 않은 알고리즘으로 보임.

/**

* Quantization => k-mean?

*/

//#define N 10

//int input[N]={3,3,3,1,2,3,2,2,2,1};

#define S 34

#define N 36

int input[N]={1,744,755,4,897,902,890,6,777,1,744,755,4,897,902,890,6,777,1,744,755,4,897,902,890,6,777,1,744,755,4,897,902,890,6,777};

int pow2(int n){

    return n*n;

}

int minError(int s, int e){

    if(s==e){

        return 0;

    }

    bool oneNumber = true;

    for(int i=s;i<e;i++){

        if(input[i]!=input[i+1]){

            oneNumber =false;

            break;

        }

    }

    if(oneNumber){

        return 0;

    }

    float mean = 0;

    for(int i=s;i<=e;i++){

        mean +=input[i];

    }

    mean = (mean/(float)((e-s)+1.0f));

    mean +=0.5f;

    int error=0;

    for(int i=s;i<=e;i++){

        error += pow2((int)mean-input[i]);

    }

    return error;

}

void sort(){

    for(int i=0;i<N;i++){

        for(int j=0;j<=i;j++){

            if(input[j] > input[i]){

                int t = input[j];

                input[j] = input[i];

                input[i]=t;

            }

        }

    }

}

int parent[S];

//minError(s,e) 의 s,e 가 무엇이 되어야 최소가 될까? s,e 는 0~N-1까지임

//0~9 S \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0개로 나누는데 가장 작은 minError 를 주는 것.

//모든 부분 조합 완전 탐색

int n=0;

int min=-1;

int minSum(int depth){

    n++;

    if(depth == S-1){

        int sum=0;

        for(int i=0;i<S-1;i++){

            sum += minError(parent[i],parent[i+1]-1);

        }

        sum+=minError(parent[depth],N-1);

        return sum;

    }

    for(int i=parent[depth]+1;i<N;i++){

        parent[depth+1]=i;

        int t=minSum(depth+1);

        if(min==-1||t<min){

            min = t;

        }

    }

    return min;

}

int main(){

    sort();

    parent[0]=0;

    printf("%d

",minSum(0));

    printf("Function %d times

",n);

    return 1;

}

#define N 5

int triangle[N][N]={

    { 6,-1,-1,-1,-1},

    { 1, 2,-1,-1,-1},

    { 3, 7, 4,-1,-1},

    { 9, 4, 1, 7,-1},

    { 2, 7, 5, 9, 4}

};

int cache[N][N];

int n=0;

int path1(int x, int y){

    n++;

    //basis

    if(x==N || y>x){return 0;}

    if(cache[x][y]!=-1){return cache[x][y];}

    int n1 = path1(x+1,y);

    int n2 = path1(x+1,y+1);

    if(n1>n2){

        return cache[x][y]=triangle[x][y]+n1;

    }else{

        return cache[x][y]=triangle[x][y]+n2;

    }

}

int main(){

    for(int i=0;i<N;i++){

        for(int j=0;j<N;j++){

            cache[i][j]=-1;

        }

    }

    printf("%d

",path1(0,0));

    printf("Function called %d times

",n);

}

/**

* JumpGame

*/

#define N 7

int gameBoard[N][N]={

    {2,5,1,6,1,4,1},

    {6,1,1,2,2,9,3},

    {7,2,3,2,1,3,1},

    {1,1,3,1,7,1,2},

    {4,1,2,3,4,1,2},

    {3,3,1,2,3,4,1},

    {1,5,2,9,4,7,-1}

};

//int gameBoard[N][N]={

//    {1,1,1,1,1,1,1},

//    {1,1,1,1,1,1,1},

//    {1,1,1,1,1,1,1},

//    {1,1,1,1,1,1,1},

//    {1,1,1,1,1,1,1},

//    {1,1,1,1,1,1,2},

//    {1,1,1,1,1,2,-1},

//};

int n=0;

int footStep[N][N];

bool jumpGame(int x,int y){

    n++;

    //basis

    if(x>=N || y>=N){ return false;}

    if(x== N -1 && y==N-1){return true;}

    if(footStep[x][y]!=-1){ return footStep[x][y];}

    footStep[x][y] = jumpGame(x+gameBoard[x][y],y) || jumpGame(x,y+gameBoard[x][y]);

    return footStep[x][y];

}

int main(){

    for(int i=0;i<N;i++){

        for(int j=0;j<N;j++){

            footStep[i][j]=-1;

        }

    }

    if(jumpGame(0,0)){

        printf("Reached a goal.

");

    }else{

        printf("Not reached a goal.

");

    }

    printf("Function called %d times

",n);

}