• 1
  • 新人请关照

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

问题描述

1
3 2
4 6 5
7 9 8 10

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

阅读 766
评论
    1 个回答

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

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

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

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

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

      撰写回答

      登录后参与交流、获取后续更新提醒

      相似问题
      推荐文章