/*
状态转移方程：

OPT(i , j)= max(OPT(i , j − 1) , max( 1+OPT(i , t − 1)+OPT(t + 1, j − 1))),

where the  max is taken over t such that bt and bj are an allowable base pair

(under conditions (i) and (ii) from the definition of a secondary structure)

*/
#include <stdio.h>

#include <stdlib.h>

#include <time.h>

#include <string.h>

#define RNALEN 9

#define LEN(X) (sizeof (X) / sizeof (X[0]))

#define MAX(X,Y) ((X < Y) ? Y : X)

char base[] = {'A', 'U', 'C', 'G'};

typedef char *string;

string generateRNA(int size)

{

    string rna = (string) malloc((size + 1) * sizeof (char) );

    string start = rna;

    string stop = rna + size;

    int index;

    srand(time(NULL));

    for (; rna < stop; rna++) {

        index = rand() % 4;

        *rna = base[index];

    }

    *rna = '\0';

    return start;

}

void testgenerate()

{

    string rna = generateRNA(RNALEN);

    printf("%s\n", rna);

}

/*

void matrix_print(char (*m)[], int len)

{

}

*/

int isMatch(char a, char b)

{

    if (a == 'A' && b == 'U')

        return 1;

    else if (a == 'U' && b == 'A')

        return 1;

    else if (a == 'C' && b == 'G')

        return 1;

    else if (a == 'G' && b == 'C')

        return 1;

    else

        return 0;

}

//核心函数：实现了状态转移方程

int opt(int (*dp)[RNALEN+1], string rna, int i, int j)

{

    int  maxPair, tmp, t;

    maxPair = 0;

    for (t = i; t < j-4; t++) {

        tmp = 0;

        if(isMatch(rna[t], rna[j])) {

            tmp++;

            if (t > i + 5) { //compute leftPair

                tmp += dp[i][t-1];

            }

            if (t < j - 6) { //comput innerPair

                tmp += dp[t+1][j];

            }

        }

        if (tmp > maxPair)

            maxPair = tmp;

    }

    return MAX(dp[i][j-1], maxPair);

}

int rna2structure(string rna, int exlen)

{

    int i, j, k;

    int dp[exlen][exlen];

    int n = exlen - 1;

    memset(dp, 0, sizeof dp);//string.h

/*

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

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

            if (j % len == 0)

                putchar('\n');

            printf("%d, ", dp[i][j]);

        }

    }

    putchar('\n');

*/

    for (k = 5; k < n; k++) {

        for (i = 1; i <= n-k; i++) {

            j = i + k;

            dp[i][j] = opt(dp, rna, i, j);

        }

    }

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

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

            if (j % exlen == 0)

                putchar('\n');

            printf("%d, ", dp[i][j]);

        }

    }

    putchar('\n');

    return dp[1][n];

}

void testStructure()

{

    string rna1 = generateRNA(RNALEN);

    //头部插入空格符，使得碱基下标从1开始

    char rna2[] = {' ', 'A', 'C', 'C', 'G', 'G', 'U', 'A', 'G', 'U', '\0'};

    char rna3[] = " ACCGGUAGU";

//    printf("len of rna2 = %d\n", LEN(rna2));

//    int maxPair = rna2structure(rna1, RNALEN+1);

    int maxPair = rna2structure(rna2, RNALEN+1);

    printf("maxPair = %d\n", maxPair);

//    rna2structure(rna3, strlen(rna3));

    //rna2structure(rna1, RNALEN);

}

int main()

{

    testgenerate();

    testStructure();

//    printf("MAX(3, 5) = %d\n", MAX(3, 5));

    return 0;

}