用c语言编写动态规划算法

动态规划是一种算法思想，适用于求解最优解问题。在C语言中，可以使用数组来实现动态规划算法。以下是一个使用动态规划解决最长公共子序列问题的示例代码：

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

#define MAX(x,y) (((x)>(y))?(x):(y))

int max(int a, int b){
    return (a>b)?a:b;
}

void lcs_dynamic(char *X, char *Y, int m, int n){
    int i,j;
    int c[m+1][n+1]; //定义用于保存最长公共子串长度的数组

    //初始化数组
    for(i=0;i<=m;i++){
        for(j=0;j<=n;j++){
            c[i][j] = 0;    
        }   
    }

    //填充数组
    for(i=1;i<=m;i++){
        for(j=1;j<=n;j++){
            if(X[i-1] == Y[j-1]){
                c[i][j] = c[i-1][j-1] + 1;
            }
            else{
                c[i][j] = max(c[i-1][j], c[i][j-1]);
            }
        }
    }

    //找到最长公共子序列
    int index = c[m][n];
    char lcs[index+1];
    lcs[index] = '\0';
    i = m;
    j = n;
    while(i>0 && j>0){
        if(X[i-1] == Y[j-1]){
            lcs[index-1] = X[i-1];
            i--;
            j--;
            index--;
        }
        else if(c[i-1][j] > c[i][j-1]){
            i--;
        }
        else{
            j--;
        }
    }

    //输出结果
    printf("\nThe longest common subsequence is: %s", lcs);
}

int main(){
    char X[100], Y[100];

    //获取输入
    printf("Enter the first string: ");
    scanf("%s", X);

    printf("Enter the second string: ");
    scanf("%s", Y);

    //计算最长公共子串
    int m = strlen(X);
    int n = strlen(Y);
    lcs_dynamic(X, Y, m, n);

    return 0;
}

在上面的代码中，我们首先定义了一个二维数组C，用于保存最长公共子串长度。然后根据初始化条件和递推公式来填充 C 数组。最后倒推出最长公共子串。