给定一个三角形, 找出自顶向下的最小路径和. 每一步只能移动到下一行中相邻的结点上.
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
例如, 给定三角形:
- [[2],
- [3,4],
- [6,5,7],
- [4,1,8,3]
- ]
自顶向下的最小路径和为
- 11
- (即, 2 + 3 + 5 + 1 = 11).
- For example, given the following triangle
- [
- [2],
- [3,4],
- [6,5,7],
- [4,1,8,3]
- ]
- The minimum path sum from top to bottom is
- 11
- (i.e., 2 + 3 + 5 + 1 = 11).
说明:
如果你可以只使用 O(n) 的额外空间 (n 为三角形的总行数) 来解决这个问题, 那么你的算法会很加分.
Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.
来源: http://www.bubuko.com/infodetail-2608829.html