题目

LeetCode.120.三角形最小路径和（中等）

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

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

题解

题目已经给出了递推公式，是从上往下取值的，所以要从最后一行往上递推，最后得到结果。
如果用递归写，这个顺序就会比较明白，递归划分为子问题后，实际是自底向上传递计算结果的。

设dp[i][j]为第i行第j列向下的最小路径和。
总共n行。

最后一行没有下一行了，所以
dp[n - 1][j] = triangle[n - 1][j]

上面的行，状态转移方程为：
dp[i][j] = triangle[i][j] + minOf(dp[i + 1][j], dp[i + 1][j + 1]

class Solution {
    fun minimumTotal(triangle: List<List<Int>>): Int {
        val n = triangle.size
        val dp = Array(n) { IntArray(n) { 0 } }
        for (j in 0 until n) {
            dp[n - 1][j] = triangle[n - 1][j]
        }
        for (i in n - 2 downTo 0) {
            for (j in 0..i) {
                dp[i][j] = triangle[i][j] + minOf(dp[i + 1][j], dp[i + 1][j + 1])
            }
        }
        return dp[0][0]
    }
}