利用动态规划方法求解数字三角形图示出了一个数字三角形宝塔。数字三角形中的数字为不超过100的整数。现规定从最顶层走到最底层，每一步可沿左斜线向下或右斜线向下走。任务一：假

Question

利用动态规划方法求解数字三角形图示出了一个数字三角形宝塔。数字三角形中的数字为不超过100的整数。现规定从最顶层走到最底层，每一步可沿左斜线向下或右斜线向下走。任务一：假设三角形行数≤10，键盘输入一个确定的整数值M，编程确定是否存在一条路径，使得沿着该路径所经过的数字的总和恰为M，若存在则给出所有路径，若不存在，则输出“NOAnswer!”字样。任务二：假设三角形行数≤100，编程求解从最顶层走到最底层的一条路径，使得沿着该路径所经过的数字的总和最大，输出最大值，并输出取得最大值的路径。

Answer 1

任务一可以枚举吧？阶数不大`` 任务二的话可以试从倒数第二行开始计算 把倒数第二行中每一个数向下加的2个和之中取较大者并记录和数及路径，这样有99个记录 再对倒数第三行做同样工作，有98个记录 如此类推即可，这样如果是用计算机做的话，可以节省相当多内存``因为记录的工作只是不断舍去一个记录并为留下来的记录只添加1个分量以记录路径