c语言 数字三角形的动态规划

从第一个元素开始往后面算,读一个数算一个数,前面的计算结果都放在result里面,后面计算时直接使用前面的计算结果。第0行(i = 0)只有一个数,直接预读,放进result里。从第1行 (i = 1)开始一边读,一边计算,每行的第一个和最后一个元素要单独计算（它们各自只有一条路往上走）。每一行第一个元素在result的位置是row_start_position = (i + 1) * i / 2; 最后一个元素位置存放在row_start_position + i里。用一维数组存放数据是为了节约空间。#include #define kMaxSize 1000#define max(a,b) ((a) > (b) (a) :(b))int main(){int result[kMaxSize];int n;scanf("%d",&n);int x;// row 0scanf("%d",&x);int maxSum = result[0] = x;// row from 1 to n - 1int row_start_position;for (int i = 1; i < n; ++i){// first element in this row// row_start_position is the starting position (in the array result) of this rowrow_start_position = (i + 1) * i / 2;scanf("%d",&x);result[row_start_position] = x + result[row_start_position - i];if (result[row_start_position] > maxSum) maxSum = result[row_start_position];// elements between the first and last,erow_start_positionclusivefor (int j = 1; j < i; ++j){scanf("%d",&x);result[row_start_position + j] = x + max(result[row_start_position + j - i - 1],result[row_start_position + j - i]);if (result[row_start_position + j] > maxSum) maxSum = result[row_start_position + j];}// the last element in this rowscanf("%d",&x);result[row_start_position + i] = x + result[row_start_position - 1];if(result[row_start_position + i] > maxSum) maxSum = result[row_start_position + i];}printf("%d\n",maxSum);return 0;} -------------二维的。-------------#include #define SIZE 100#define max(a,b) ((a) > (b) (a) :(b))int main(){int data[SIZE][SIZE];int n;scanf("%d",&n);scanf("%d",data[0]);int maxSum = data[0][0];for(int i = 1; i < n; ++i){scanf("%d",data[i]);data[i][0] += data[i - 1][0];maxSum = max(maxSum,data[i][0]);for(int j = 1; j < i; ++j){scanf("%d",data[i] + j);data[i][j] += max(data[i - 1][j - 1],data[i - 1][j]);maxSum = max(maxSum,data[i][j]);}scanf("%d",data[i] + i);data[i][i] += data[i - 1][i - 1];maxSum = max(maxSum,data[i][i]);}printf("%d\n",maxSum);return 0;} ---------------从下往上数第二层开始,每一个元素必定有两个方向。从下往上的代码更简洁。---------------#include #define max(a,b) ((a) > (b) (a) :(b))#define kMaxSize 101int result[kMaxSize][kMaxSize];int main(){int n;scanf("%d",&n);for (int i = 0; i < n; ++i)for (int j = 0; j = 0; --i)for (int j = 0; j