由于自己的算法不太好，在学习动态规划时参考了一些别人大佬的博客。下面是我在学习时参考的文章。
矩阵连乘问题
理解文章后，我的代码如下：
#include<stdio.h> void calculate(int m, int n, int rc[], int table[][100], int s[][100]);//求解表中每一个值的具体过程 void Matrix(int n, int rc[], int table[][100], int s[][100]);//填表 void output(int x, int y, int s[][100]);//输出加括号的结果 /* 参数说明： table[][] Ai...Aj连乘的最少次数 rc[] 每个矩阵的行列信息 s[][] Ai...Aj连乘的最优解第一层断开位置 count1 控制行下标的输入 count2 控制列下标的输入 rc数组中存储的信息： 0 —(n-1) A0 —An-1的行信息 n —(2*n-1) A0 —An-1的列信息 */ /* 解题关键： 1.题目信息： 给定n个矩阵{A1,A2,...,An}，其中Ai与Ai+1是可乘的（i=1,2,...,n-1） 2.理解矩阵连乘: A是一个p×q矩阵，B是一个q×r矩阵，AB相乘，得到矩阵元素个数为p×r,每个元素由q次乘法得到， 因此需要乘法次数p×q×r 3.利用table已知数值 计算table[i][j]只会使用到它的左下方的矩阵元素数值，因此填table的数据从下至上，从左到右 */ /* 测试数据： 6 30 35 35 15 15 5 5 10 10 20 20 25 结果: 15125 ((A1(A2A3))((A4A5)A6)) */ int main() { int n; scanf("%d", &n); int table[n+1][100] = {0}; int rc[2*n]; int s[n+1][100]; int count1 = 0, count2 = n; for(int i = 0; i < 2*n; i++) { if(i%2 == 0) { scanf("%d", &rc[count1]); count1++; } else { scanf("%d", &rc[count2]); count2++; } } Matrix(n, rc, table, s); printf("%d", table[1][n]); output(1, n, s); /* 调试助手 for(int i = 0; i < 2*n; i++) printf("%4d", rc[i]); printf("\n"); for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { printf("%10d", table[i][j]); } printf("\n"); }*/ return 0; } void calculate(int m, int n, int rc[], int table[][100], int s[][100], int N) { table[m][n] = table[m][m] + table[m+1][n] + rc[m-1]*rc[m+N-1]*rc[n-1+N]; s[m][n] = m; for(int i = m+1; i < n; i++) { int temp = table[m][i] + table[i+1][n] + rc[m-1]*rc[i+N-1]*rc[n-1+N]; if(temp < table[m][n]) { table[m][n] = temp; s[m][n] = i; } } } void Matrix(int n, int rc[], int table[][100], int s[][100]) { for(int i = n; i > 0; i--) { for(int j = i; j <= n; j++)//保证填表的右上角部分 { if(i == j) table[i][j] = 0; else calculate(i, j, rc, table, s, n); } } } void output(int x, int y, int s[][100]) { if(x == y)//递归调用的出口 printf("A%d", x); else { printf("("); int temp = s[x][y]; output(x,temp,s); output(temp+1,y,s); printf(")"); } }
最大子段和
#include<stdio.h> void cal(int n, int arr[], int max[], int s[]); /* 参数说明： arr[] 存储每个数据 max[] 从头到i为止最大的子段和 s[] 状态，记录到目前为止最大字段和的上一个元素的下标 */ /* 测试数据： 6 -2 11 -4 13 -5 -2 测试结果： 20 11 -4 13 */ int main() { int n; scanf("%d", &n); int arr[n]; for(int i = 0; i < n; i++) scanf("%d", &arr[i]); int max[n]={0}; int s[n]={0}; cal(n, arr, max, s); int m = max[0]; int index = 0; for(int i = 1; i < n; i++) if(m < max[i]) { m = max[i]; index = i; } printf("%d\n", m); int record = index; while(index != s[index]) { index = s[index]; } for(int i = index; i <= record; i++) printf("%5d", arr[i]); return 0; } void cal(int n, int arr[], int max[], int s[]) { max[0] = arr[0]; s[0] = 0; for(int i = 1; i < n; i++) { if(arr[i] < max[i-1]+arr[i]) { max[i] = max[i-1]+arr[i]; s[i] = i-1; } else { max[i] = arr[i]; s[i] = i; } } }
附加：分治法解法
#include<stdio.h> int cal(int arr[], int lborder, int rborder, int *lbegin, int *rend); /* 参数解释： arr[] 数据数组 lbegin 当前最大字段和开始下标 rend 当前最大字段和结束下标 lborder 数据开始下标 rborder 数据结束下标 */ int main() { int n; scanf("%d", &n); int arr[n]; for(int i = 0; i < n; i++) scanf("%d", &arr[i]); int lbegin, rend; int max = cal(arr, 0, n-1, &lbegin, &rend); printf("%d\n", max); for(int i = lbegin; i <= rend; i++) printf("%4d", arr[i]); return 0; } int cal(int arr[], int lborder, int rborder, int *lbegin, int *rend) { if(lborder == rborder) { *lbegin = lborder; *rend = rborder; return arr[lborder]; } else { int center = (lborder+rborder)/2; int lmax = cal(arr, lborder, center, lbegin, rend); //临时左边最大字段和开始结束下标记录 int ltempbegin = *lbegin; int ltempend = *rend; int rmax = cal(arr, center+1, rborder, lbegin, rend); //临时右边最大字段和开始结束下标记录 int rtempbegin = *lbegin; int rtempend = *rend; int lc = arr[center]; int rc = arr[center+1]; int temp = 0; //临时中间最大字段和开始下标记录 int ctempbegin = center; for(int i = center; i >= lborder; i--) { temp += arr[i];//保证结果是连加结果 if(temp > lc) { lc = temp; ctempbegin = i; } } temp = 0; //临时中间最大字段和结束下标记录 int ctempend = center+1; for(int j = center+1; j <= rborder; j++) { temp += arr[j];//保证结果是连加结果 if(temp > rc) { rc = temp; ctempend = j; } } int max = lc+rc; *lbegin = ctempbegin; *rend = ctempend; if(lmax > max) { max = lmax; *lbegin = ltempbegin; *rend = ltempend; } if(rmax > max) { max = rmax; *lbegin = rtempbegin; *rend = rtempend; } return max; } }
参考文章：最大子段和详解（N种解法汇总）
最长单调子序列
#include<stdio.h> void cal(int arr[], int table[], int s[], int n); /* 整体思路： 利用i之前的数据，计算从arr[0]到arr[i],必须包括arr[i]的最长递增子序列 table[] 记录以下标i为最后一个元素的递增子序列，序列的个数 s[] 记录table[i]最长递增子序列利用到的上一个元素下标，如果序列数量为1的话，值即设为自己的下标i 检测样例： 8 5 2 8 6 3 6 5 7 */ int main() { int n; scanf("%d", &n); int arr[n]; for(int i = 0; i < n; i++) scanf("%d", &arr[i]); int table[n] = {1}; int s[n] = {0}; cal(arr, table, s, n); //计算递增子段和的最大值 int max = table[0]; int index = 0; for(int i = 1; i < n; i++) { if(table[i] > max) { index = i; max= table[i]; } } printf("%d\n", max); // printf("index = %d\n", index); //根据s数组的内容找出最大递增子段和的每个元素（逆序的） //t中间数组帮助正序输出最大递增子段和的每个元素 int t[max]; int count = 0; for(;;) { // printf("%d ", arr[index]); t[count] = arr[index]; count++; index = s[index]; if(s[index] == index) { // printf("%d ", arr[index]); t[count] = arr[index]; break; } } //正序输出每个元素 for(int i = max-1; i >= 0; i--) printf("%d ", t[i]); /* printf("\n"); for(int i = 0; i < n; i++) printf("%4d", i); printf("\n"); for(int i = 0; i < n; i++) printf("%4d", arr[i]); printf("\n"); for(int i = 0; i < n; i++) printf("%4d", table[i]); printf("\n"); for(int i = 0; i < n; i++) printf("%4d", s[i]); */ return 0; } void cal(int arr[], int table[], int s[], int n) { for(int i = 1; i < n; i++) { //默认最长子序列的长为1.即只有自己一个元素 int tlen = 1; for(int j = 0; j < i; j++) { if(arr[i] > arr[j] && tlen < table[j]+1) { tlen = table[j]+1; s[i] = j; } } table[i] = tlen; if(tlen == 1) s[i] = i; } }