c语言实现动态规划之RNA二级结构预测，输入指定的碱基序列，输出备忘录和标记函数

以下是C语言实现RNA二级结构预测的动态规划代码，包括备忘录和标记函数：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_N 1000

int N;  // RNA序列长度
char S[MAX_N+1]; // RNA序列
int memo[MAX_N][MAX_N];  // 备忘录，用于记录计算结果
int mark[MAX_N][MAX_N];  // 标记函数，用于记录最优解路径

// 计算区间[i,j]的最优解
int dp(int i, int j) {
    if (memo[i][j] != -1) {
        return memo[i][j];  // 如果已经计算过，则直接返回备忘录中的结果
    }
    if (i >= j) {
        return 0;  // 区间长度小于等于1时，无法形成二级结构，返回0
    }
    int res = 0;
    if ((S[i] == 'A' && S[j] == 'U') || (S[i] == 'U' && S[j] == 'A') || (S[i] == 'G' && S[j] == 'C') || (S[i] == 'C' && S[j] == 'G')) {
        // 如果i和j可以配对，则考虑i和j配对的情况
        int tmp = dp(i+1, j-1) + 1;
        if (tmp > res) {
            res = tmp;
            mark[i][j] = 1;  // 标记[i,j]为匹配
        }
    }
    // 如果i和j不能配对，则考虑i和[k,j]配对的情况，k属于[i+1,j-1]
    for (int k = i+1; k <= j-1; k++) {
        int tmp = dp(i, k-1) + dp(k+1, j);
        if (tmp > res) {
            res = tmp;
            mark[i][j] = k;  // 标记[i,j]为不匹配，但i和k、k+1和j匹配
        }
    }
    memo[i][j] = res;  // 将计算结果保存到备忘录中
    return res;
}

// 输出RNA序列的最优解路径
void print_mark(int i, int j) {
    if (i >= j) {
        return;
    }
    if (mark[i][j] == 1) {
        printf("%d %d\n", i+1, j+1);  // 输出配对的位置
        print_mark(i+1, j-1);
    } else {
        int k = mark[i][j];
        print_mark(i, k-1);  // 输出不配对的左半部分
        print_mark(k+1, j);  // 输出不配对的右半部分
    }
}

int main() {
    scanf("%s", S);
    N = strlen(S);
    memset(memo, -1, sizeof(memo));  // 初始化备忘录
    memset(mark, 0, sizeof(mark));  // 初始化标记函数
    printf("%d\n", dp(0, N-1));  // 输出RNA序列的最优解
    print_mark(0, N-1);  // 输出RNA序列的最优解路径
    return 0;
}

在该代码中，dp函数用于计算区间[i,j]的最优解，它考虑了两种情况：

1. 如果i和j可以配对，则考虑i和j配对的情况。
2. 如果i和j不能配对，则考虑i和[k,j]配对的情况，k属于[i+1,j-1]。

同时，备忘录memo和标记函数mark也被引入，用于记录计算结果和最优解路径。其中，memo[i][j]表示区间[i,j]的最优解，mark[i][j]标记了区间[i,j]的最优解路径。

最后，我们通过调用dp函数和print_mark函数，分别输出RNA序列的最优解和最优解路径。