Skip to content

Latest commit

 

History

History

119. Triangle

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 
 
 

这道题的思路可以参考前面的两道题:[32. Pascal's Triangle](../32. Pascal's Triangle) 和 [38. Minimum Path Sum](../38. Minimum Path Sum)

其共同点都是用到了 DP 的思想。

DP, 即动态规划,的本质在哪?一句话:“前事不忘后事之师”。说白了,就是善于积累,不做重复劳动。

杨辉三角,下一行来自上一行的积累;最小路径,每一格基于左上两格的判断。

这道题,求依然是最小路径,所以还是积累的问题。


我们从例子开始分析,我们希望:每向下一行,能够使得下一行的元素成为他们能够成为最小的路径和,如何理解?

[2] -> [3,4] : [5,6]
[3,4] -> [6,5,7] : [9, 8, 11]
// 可以发现一个基本规律,即 front 和 back 前后两个元素是没得选的,他们的路径和来自上一个 vector 的首尾。
// 而中间的元素,可选择的公式为:
v[i] += min(steps[i-1], steps[i]); // v 代表下一行的 vector, steps 代表上一行累计过的 vector.

而我们想要的最小路径和,就是迭代完整个三角形之后 steps 中最小的那个值。

代码非常简单。 不赘述了。