120. Triangle

给定一个三角形，计算从顶到底最小的路径和

1
2
3
4
5
6
[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

思路： 6 star, 求路径和最小值， 最大最小值首先考虑动态规划， 从底层到顶层按层遍历，状态转移方程 dp[j] = triangle[i][j] + min(dp[j], dp[j+1])
dp[i]表示从底层到当前层的第i个元素的路径中最小的和，比较巧妙

Python:

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def minimumTotal(self, triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        """
        length = len(triangle)
        dp = triangle[-1]
        for i in range(length-2, -1, -1): # 从倒数第二行开始，一直到第一行
            for j in range(i+1):   # 在每一行计算时，从前到后
                dp[j] = triangle[i][j] + min(dp[j], dp[j+1])
        return dp[0]

Go:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func minimumTotal(triangle [][]int) int {
	var min int
	length := len(triangle)
	dp := triangle[length-1]
	for i := length-2; i > -1; i-- {
		for j := 0; j < i+1; j++ {
			min = dp[j]
			if dp[j+1] < min {
				min = dp[j+1]
			}
			dp[j] = triangle[i][j] + min
		}
	}
	return dp[0]
}