posts - 99, comments - 8, trackbacks - 0

//利用aMaxSum来标记该位置坐标上的值是否被计算过了，如果被计算了直接利用原来已经存在aMaxSum中的值
//递归是一个比较难以理解的知识，最好的方法是自己通过画出递归调用图来理解中间的过程
//动态规划是以递归为基础的，需要解决的是将递归中出现的重复子问题记录下来，以减少下次递归时的重复计算从而减少时间复杂度；

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

int a[101][101];

int n;

int aMaxSum[101][101];

int max_sum (int r,int j)

{

if ( r == n - 1)

return a[r][j];

if (aMaxSum[r + 1][j] == -1)

aMaxSum[r + 1][j] = max_sum (r + 1, j);

if (aMaxSum[r + 1][j + 1] == -1)

aMaxSum[r + 1][j + 1] = max_sum (r + 1, j + 1);

if ( aMaxSum[r + 1][j] > aMaxSum[r + 1][j + 1])

return aMaxSum[r + 1][j] + a[r][j];

else

return aMaxSum[r + 1][j + 1] + a[r][j];

}

int main ()

{

while ( scanf ("%d", &n) != EOF )

{

for (int i = 0; i < n; i ++)

{

for (int j = 0; j < i+ 1; j ++ )

{

scanf ("%d", &a[i][j]);

}

memset (aMaxSum, -1, sizeof (aMaxSum));

int max = max_sum (0,0);

printf ("%d\n", max);

}

return 0;

}

posted on 2010-08-14 10:54 雪黛依梦阅读(124) 评论(0) 编辑收藏引用

只有注册用户登录后才能发表评论。
【推荐】100%开源！大型工业跨平台软件C++源码提供，建模，组态！



网站导航: 博客园 IT新闻 BlogJava 知识库博问管理

2010年8月

日

一

二

三

四

五

六

常用链接

留言簿(4)

随笔分类

随笔档案

文章档案

2010年8月 (1)

常用链接

留言簿(4)

随笔分类

随笔档案

文章档案

搜索

最新评论

阅读排行榜

评论排行榜