从顶层开始向下走，每走下一级，可向左下方向或右下方向走。求走到底层后它所经过数字的总和的最大值。
【输入格式】
第一个整数为n,一下n行为各层的数字。
【输出格式】
一个整数，即最大值。
【输入样例 】
5
1
6 3
8 2 6
2 1 6 5
3 2 4 7 6
【输出样例】
23
【样例说明】
最大值=1+3+6+6+7=23
递归算法
思路：f(x,y)=a(x,y)+max(f(x+1,y),f(x+1,y+1))
特点：
（1）有些f(x,y)会重复计算
（2）所有点都计算了
记忆化搜索
思路：和递归算法一样，只不过一旦计算到f(x,y)就记录下来
特点：
（1）与递归相比没有重复计算
DFS
思路：每次先加上当前a(i,j),如果此时已经在最后一层，并且此时之和大于最大值，最大值更新，返回结束，如果不是在最后一层则执行dfs(i+1,j)和dfs(i+1,j+1),只和减去a(i+1,j)或a(i+1,j+1)，因为若其中一个达到了最大则此时应该程序返回结束了，若还没有则一定不是最大的，执行另外一个
总结：DFS的最坏情况是记忆化搜索，其他情况计算量均小于他
To be continued......
不足之处，多多指教
参考资料
https://blog.csdn.net/weixin_38391092/article/details/79590710
网友评论