求教这个简单算法怎么写？

Question

问题描述

1
3 2
4 6 5
7 9 8 10

从上往下走，每次只能走左(L)或右(R)走一步， 然后将数字加起来，找出值最大的路径和最大值。
这个算法 用python要怎么写？

Answer 1

有个思路，创建一个二维数组aux，储存当前位置的最大值，最后只需要返回整个二维数组的最大值。

路径就最后用DFS倒推出来。

例如题目的例子，创建的aux最终是这个样子

[ [ 1 ], 
  [ 4, 3 ],
  [ 8, 10, 8 ],
  [ 15, 19, 18, 18 ]]

时间复杂度是O(1/2*n^2)，n是数组的长度，这里是4。