120.三角形最小路径和

动态规划+空间优化

状态转移方程： dp[i][j] = triangle[i][j] + min(dp[i-1][j], dp[i-1][j-1])

应该记录一个二维数组dp，来维护每个位置的最小路径。但是由于是三角形结构，dp[i][j] 只跟 dp[i-1][j-1] 和 dp[i-1][j] 有关，使用一个一维数组来记录dp，倒序遍历，则计算
i 行的 dp[j] 时，dp[j-1] 和 dp[j] 还是 i-1 行的数据，并不影响计算。

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

func minimumTotal(triangle [][]int) int {
    // dp[i][j] = triangle[i][j] + min(dp[i-1][j], dp[i-1][j-1])

    n := len(triangle)

    if n == 1 {
        return triangle[0][0]
    }

    dp := make([]int, n)
    dp[0] = triangle[0][0]
    ans := math.MaxInt

    for i := 1; i < n; i++ {
        for j := i; j >= 0; j-- {
            if j == 0 {
                dp[j] += triangle[i][j]
            } else if j == i {
                dp[j] = triangle[i][i] + dp[j-1]
            } else if dp[j] < dp[j-1] {
                dp[j] = triangle[i][j] + dp[j]
            } else {
                dp[j] = triangle[i][j] + dp[j-1]
            }

            if i == n - 1 {
                if dp[j] < ans {
                    ans = dp[j]
                }
            }
            
        }
    }

    return ans
}