120.三角形最小路径和.md

120. 三角形最小路径和

url

题目

给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
解释：如下面简图所示：
   2
  3 4
 6 5 7
4 1 8 3
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

方法

code

js

let minimumTotal = triangle => {
    if (triangle.length === 0)
        return 0;
    let row = triangle.length;
    let dp = Array(row).fill(0).map(_ => Array(triangle[row-1].length).fill(0));
    // 初始化
    for (let i = 0; i < row; i++) {
        for (let j = 0; j < triangle[i].length; j++) {
            dp[i][j] = triangle[i][j];
        }
    }
    // 从下往上，初始化最后一行
    for (let i = 0; i < triangle[row-1].length; i++) {
        dp[row-1][i] = triangle[row-1][i];
    }
    // dp
    for (let i = row-2; i >= 0; i--) {
        for (let j = 0; j < triangle[i].length; j++) {
            dp[i][j] = Math.max(dp[i+1][j], dp[i+1][j+1]) + triangle[i][j];
        }
    }
    return dp[0][0];
}

go

func minimumTotal(triangle [][]int) int {
	Min := func(a, b int) int {
		if a < b {
			return a
		} else {
			return b
		}
	}
	if len(triangle) == 0 {
		return 0
	}
	row := len(triangle)
	dp := make([][]int, row)
	for i := range dp {
		dp[i] = make([]int, len(triangle[row-1]))
	}
	// 初始化
	for i := 0; i < row; i++ {
		for j := 0; j < len(triangle[i]); j++ {
			dp[i][j] = triangle[i][j]
		}
	}
	// 从下往上，初始化最后一行
	for i := 0; i < len(triangle[row-1]); i++ {
		dp[row-1][i] = triangle[row-1][i]
	}
	// dp
	for i := row-2; i >= 0; i-- {
		for j := 0; j < len(triangle[i]); j++ {
			dp[i][j] = Min(dp[i+1][j], dp[i+1][j+1]) + triangle[i][j]
		}
	}
	return dp[0][0]
}

java

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        if(triangle.size() == 0) return 0;
        int row = triangle.size();
        int[][] dp = new int[row][triangle.get(row - 1).size()];
        // 初始化
        for(int i = 0; i < row; i++) {
            for (int j =0; j < triangle.get(i).size(); j++) {
                dp[i][j] = triangle.get(i).get(j);
            }
        }
        // 从下往上， 初始化最后一行
        for (int i = 0; i < triangle.get(row - 1).size(); i++) {
            dp[row - 1][i] = triangle.get(row - 1).get(i);
        }
        // 动态规划
        for (int i = row - 2; i >= 0; i--) {
            for (int j = 0; j < triangle.get(i).size(); j++) {
                dp[i][j] = Math.min(dp[i+1][j], dp[i+1][j+1]) + triangle.get(i).get(j);
            }
        }
        return dp[0][0];
    }
}