120. 三角形最小路径和

解法一：回溯

走所有的路径，计算每条路径的和，再判断最小值。

时间复杂度：O( 2^n )

解法二：动态规划

1. 状态的定义：从下往上推，定义DP[ i , j ]，存储从最下面的节点走到[ i , j ]这个点的路径和最小值。[ 0 , 0 ]点为最终结果。
2. DP方程：DP[ i , j ] = min( DP[ i + 1 , j ] , DP[ i + 1 , j + 1] ) + Triangle[ i , j ]

对于最下面的一行，就是节点本身了。所以 DP[ m – 1 , j ] = Triangle[ m – 1 , j ]

时间复杂度 O( m * n )

代码：

这里需要想明白递推公式，为什么要从下往上递推。以及优化的点，为什么只需要最后一行大小的数组即可。

详细题解：https://leetcode-cn.com/problems/triangle/solution/zi-di-xiang-shang-dong-tai-gui-hua-lei-si-yu-cong-/

class Solution {
    fun minimumTotal(triangle: List<List<Int>>): Int {

        val mini = triangle[triangle.size - 1].toIntArray()
        for (i in triangle.size - 2 downTo 0)
            for (j in triangle[i].indices) {
                mini[j] = triangle[i][j] + Math.min(mini[j], mini[j + 1])
            }
        return mini[0]
    }
}