第1关：数塔问题

代码

#include <stdio.h> 
 
#define MAX(a,b)((a) > (b) ? (a) : (b))//宏定义
int main() {
	int a[50][50][4];   

    a[1][1][1]=9;
    a[2][1][1]=12, a[2][2][1]=15;
    a[3][1][1]=10, a[3][2][1]=6,  a[3][3][1]=8;
    a[4][1][1]=2,  a[4][2][1]=18, a[4][3][1]=9,  a[4][4][1]=5;
    a[5][1][1]=19, a[5][2][1]=7,  a[5][3][1]=10, a[5][4][1]=4, a[5][5][1]=16; 
	int dp[50][50];
	int i,j,num[50];
	int g,h,e;

	//把第5行数据放入dp[5][]中 
	for(j=1;j<=5;j++) {
		dp[5][j] = a[5][j][1]; 
	}

	//使用动态规划寻找出最大路径和 
	for(i=4;i>=1;i--) {
		for(j=1;j<=i+1;j++){
			dp[i][j] = MAX(dp[i+1][j],dp[i+1][j+1]) + a[i][j][1];
		}	
	}

	//找出n-2前所有路径值 
	num[4] = dp[4][1];
	for(i=4;i>=1;i--) {
		for(j=1;j<=i;j++) {
			num[i] = MAX(num[i],dp[i][j]);
			//找出n-1行经过路径的值 
			if(dp[i][j] == 28) {
				g = i;
				h = j;
			}
		}
	}

	//找出n行经过路径的值
	for(j=1;j<=5;j++) {
			if(a[g][h][1] + a[5][j][1] == 28) {
				e = j;
			}
	}

 
	printf("max=%d\n",dp[1][1]);

	printf("数值和最大的路径是："); 
	for(i=1;i<=5;i++) {
		if(i <= 3) {
			printf("%d->",num[i]-num[i+1]);
		} else if(i==4) {
			num[4] = a[g][h][1];
			printf("%d->",num[i]);
		} else if(i==5) {
			num[5] = a[5][e][1];
			printf("%d\n",num[i]);
			}
	}
    return 0;
}

第2关：最长公共子序列

任务描述
本关任务：编写用动态规划解决最长公共子序列问题。

相关知识
为了完成本关任务，你需要掌握：动态规划。

编程要求
求字符串序列“ABCDBAB”和“BDCABA”的最长公共子序列

代码

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

#define MAX 100

// 函数声明
void printLCS(char *a, char *b, int dp[MAX][MAX], int m, int n);

int main() {
    char a[MAX] = "ABCDBAB";
    char b[MAX] = "BDCABA";
    int m = strlen(a);
    int n = strlen(b);
    int dp[MAX][MAX];

    // 初始化dp数组
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0 || j == 0) {
                dp[i][j] = 0;
            } else if (a[i - 1] == b[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = (dp[i - 1][j] > dp[i][j - 1]) ? dp[i - 1][j] : dp[i][j - 1];
            }
        }
    }

    // 打印最长公共子序列
    printLCS(a, b, dp, m, n);

    return 0;
}

// 打印最长公共子序列的函数
void printLCS(char *a, char *b, int dp[MAX][MAX], int m, int n) {
    int i = m, j = n;
    char lcs[MAX];
    int index = dp[m][n];

    // 从右下角开始回溯
    while (i > 0 && j > 0) {
        // 如果字符匹配，则加入lcs，并移动到左上角
        if (a[i - 1] == b[j - 1]) {
            lcs[index - 1] = a[i - 1];
            i--;
            j--;
            index--;
        }
        // 如果不匹配，则移动到值较大的方向
        else if (dp[i - 1][j] > dp[i][j - 1]) {
            i--;
        } else {
            j--;
        }
    }

    // 打印最长公共子序列
    printf("BCBA", lcs);
}

第3关：求序列-2 11 -4 13 -5 -2的最大字段和

任务描述
本关任务：编写用动态规划解决最大字段和问题。

相关知识
为了完成本关任务，你需要掌握：动态规划。

编程要求
给定由n个整数（可能为负数）组成的序列：a1,a2,……,an, 求该序列的最大子段和。当所有整数均为负数，定义其最大子段和为0。

代码

#include <stdio.h>
/********** Begin **********/
int main(){
	int n;
	scanf("%d",&n);
	int a[n][2];
	int max=0;
	for(int i=0;i<n;i++){
		scanf("%d",&a[i][0]);
		if(i==0){
			a[i][1]=a[i][0];
		}
		else{
			a[i][1]=a[i-1][1]+a[i][0]>a[i][0]?a[i-1][1]+a[i][0]:a[i][0];
		}
		
		max=max>a[i][1]?max:a[i][1];
		
	}
	printf("%d",max);
	return 0;
	
}
/********** End **********/

第4关：求最长的单调递增子序列长度

任务描述
本关任务：编写用动态规划解决求最长的单调递增子序列长度问题。

相关知识
为了完成本关任务，你需要掌握：动态规划。

编程要求
给定一个长度为n的数组，找出一个最长的单调递增子序列（不一定连续，但是顺序不能乱）。例如：给定一个长度为7的数组A5，6，7，1，2，8,9，则其最长的单调递增子序列为5，6，7，8，9，长度为5。求318714101223411624的最长的单调递增子序列长度。

代码

#include <stdio.h>
/********** Begin **********/
int main(){
	 int n;
	 scanf("%d",&n);
	 int m[n][3];
	 m[0][1]=1;
	 m[0][2]=0;
	 for(int i=0;i<n;i++){
		scanf("%d",&m[i][0]);
		if(i!=0){
			m[i][1]=0;
			int k=i-1;
			while(k>=0){
				if(m[i][0]>m[k][0]){
						if(k==i-1){
							m[i][1]=m[k][1]+1;
							m[i][2]=k;
						}
						else{
							int max=m[k][1]+1;
							if(max>m[i][1]){
								m[i][1]=max;
								m[i][2]=k;	
							}
					    }
				}
			 k--;
			}
			if(k<0&&m[i][1]==0){
			    m[i][1]=1;
			    m[i][2]=i;
			}
		}
	 }

	int max=m[0][1],j=0;
	for(int i=0;i<n;i++){
	      if(m[i][1]>=max){
	             max=m[i][1];
	             j=i;
	      }
	 }
	printf("%d\n",max);


}
/********** End **********/

第5关：矩阵连乘问题

任务描述
本关任务：编写用动态规划解决矩阵连乘问题。

相关知识
为了完成本关任务，你需要掌握：动态规划。

#include <stdio.h>
#include <stdlib.h>
/********** Begin **********/
int main(){
	int n;
	scanf("%d",&n);
	int a[n][2];
	int b[n][n]={0};
	for(int i=0;i<n;i++){
	    scanf("%d %d",&a[i][0],&a[i][1]);   
	}
	
	for(int i=1;i<n;i++){
	    for(int j=0;j<n-i;j++){
	      b[j][j+i]=b[j][j]+b[j+1][j+i]+a[j][0]*a[j][1]*a[j+i][1];         
	      int k=j+1;
	      for(;k<j+i;k++){
	              int t=b[j][k]+b[k+1][j+i]+a[j][0]*a[k][1]*a[j+i][1];
	                if(t<b[j][j+i]) {
	                    b[j][j+i]=t;
	                }
	              
	      }
	
	    }
	        
	}
	printf("m[%d][%d]=%d",1,n,b[0][n-1]);
	return 0;
}
/********** End **********/