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

c语言 数字三角形的动态规划
给你一个数字三角形,形式如下:
1
2 3
4 5 6
7 8 9 10
找出从第一层到最后一层的一条路,使得所经过的数字之和最大.
（每个数字可经过其左上或右上的数）
第一行输入行数 下面输入下三角矩阵
只需要输出最大的和
我的代码如下,可是太耗时,谁知道如何改进来节省时间啊?
#include "stdafx.h"
int b(int a[][100],int n,int i,int j)
{
if(ib(a,n,i+1,j+1)?b(a,n,i+1,j):b(a,n,i+1,j+1);
return(a[i][j]+c);
}
else if(i==n-1)
return(a[i][j]);
}
void main()
{
int n,a[100][100],i,j;
scanf("%d",&n);
for(i=0;i

从第一个元素开始往后面算,读一个数算一个数,前面的计算结果都放在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 = 0; --i)
for (int j = 0; j