求助 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 0
scanf("%d", &x);
int maxSum = result[0] = x;

// row from 1 to n - 1
int 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 row
row_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_positionclusive
for (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 row
scanf("%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 101
int result[kMaxSize][kMaxSize];

int main()
{
int n;

scanf("%d", &n);
for (int i = 0; i < n; ++i)
for (int j = 0; j <= i; ++j)
scanf("%d", result[i] + j);

for (int i = n - 2; i >= 0; --i)
for (int j = 0; j <= i; ++j)
result[i][j] += max(result[i + 1][j], result[i + 1][j + 1]);

printf("%d\n", result[0][0]);
return 0;
}

你这样递归 很耗内存 也很耗时

使用动态规划

每计算一次 保存一次 下次直接取
比如 从第一层 到第二层的每个路径保存在一个数组里
从第二层到第三层 计算的时候 计算从第二层的每个到第三层的路径 加上第一层到第二层的路径（这部分直接从数组里面取） 然后保存第一层到第三层每个数的路径 供以后计算

这样只计算一次 就可以了 不是每次都计算
看看动态规划算法 。。。。