示出了一个数字三角形。 请编一个程序计算从顶至底的某处的一条路径，使该路径所经过的数字的总和最大。每一步可沿左斜线向下或右斜线向下走；1<三角形行数<25；三角形中的数字为整数<1000；  路径所经过的数字的总和最大的答案
  偶然看到的一题，，，该怎么做？？

方法有很多~一个是递归~另一个是贪心算法(实质就是简单的运用广度搜索原理求局部最优解集合)最近敲数据结构敲多了~竟然想到了广度搜索和遍历二叉树(玩笑~应该考算法没那么复杂)~好像中间一部分数字取不了~可以排除~


思路~每一个可以走到的位置都有一个唯一确定的步数~这个步数可以轻易算出~然后求从步数从小到大的每个步数的最优解~感觉这是一个动态规划问题~

[此贴子已经被作者于2017-3-12 17:53编辑过]

附加简单算法~

1
     2
3       3
     4     4
5       5     5
    6       6     6
7     7        7     7
    8     8        8     8
9    9        9       9      9

这些数字代表走到该点的步数~
递推出这些数字的最优解~

好像这样不用递归也行耶~思路一目了然了~

实质就是简单的运用广度搜索原理求局部最优解集合


这个是什么 我们还没学。。。。

其实这个可以是深入浅出~
第一次求所有第一步的最大值~
第二次求所有第二步的最大值~
第n次求所有第n步的最大值~
由于一个确定的位置最多只能由两个上一步的位置推出来~所以位置解就是求左斜上方和斜右斜上方的位置(如果有的话)的较大值~

[此贴子已经被作者于2017-3-12 16:54编辑过]

  必须用这代码。？？这代码  不太认识。。。。

我怎么算出来等于40呢？5+7+8+8+7+5＝40

第一行的5是指行数而不是内容~按你这样的算法这题就非常简单了~

能否  把你所想的代码写下。。。。

  这个我也不清楚。。