120. 三角形最小路径和

题意：

解题思路：

思路：Time: O(n^2), Space: O(n^2)
状态表示: dp(i, j): 从最下层走到坐标i, j的所有路径中的 最小和dp(0, 0) 为所求
转移方程 : dp(i, j) = min(dp(i+1, j), dp(i+1, j+1)) + triangle(i, j) 
  第三层：6:[2,0] = 7; 5:[2,1] = 6; 7:[2,2] = 10;
  第二层：3:[1, 0] = min([3+7],[3+6]) = 9;
  第二层：4:[1, 1] = min([4+6],[4+10]) = 10  
  第一层  2:[0,0] = min(9, 10) + 2;

PHP代码实现：

class Solution {
    // Time: O(n^2), Space: O(n^2)
    function minimumTotal($triangle) {
        $n = count($triangle);
        $dp[$n - 1] = $triangle[$n - 1];// 最底层每个元素到达底部的最小路径
        for ($i = $n - 2; $i >=0; $i--) {// 自下而上动态规划
            for ($j = 0; $j < count($triangle[$i]); $j ++) {
                $dp[$i][$j] = min($dp[$i+1][$j], $dp[$i+1][$j+1]) + $triangle[$i][$j];
            }
        }
        return $dp[0][0];
    }
    //自上而下
    // Time: O(n^2), Space: O(n^2)
    function minimumTotalTopDown($triangle) {
        $n = count($triangle);
        $dp[0][0] = $triangle[0][0];
        for ($i = 1; $i < $n; $i++) {
            $dp[$i][0] = $dp[$i-1][0] + $triangle[$i][0];
            $dp[$i][$i] = $dp[$i - 1][$i - 1] + $triangle[$i][$i];
            for ($j = 1; $j < $i; $j++) {
                $dp[$i][$j] = min($dp[$i - 1][$j - 1], $dp[$i - 1][$j]) + $triangle[$i][$j];
            }
        }
        return min($dp[$n - 1]);
        /*
        $min = $dp[$n - 1][0];
        for ($i = 1; $i < $n; ++$i) {
            $min = min($min, $dp[$n - 1][$i]);
        }
        return $min;*/
    }
    //递归超时
    function minimumTotalRecursive($triangle) {
        return $this->dfs(0, 0, $triangle);
    }
    function dfs($x, $y, $triangle) {
        if ($x == count($triangle)) return 0;
        return $triangle[$x][$y] + min($this->dfs($x+1, $y, $triangle), $this->dfs($x + 1, $y + 1, $triangle));
    }
}

GO代码实现：

func minimumTotal(triangle [][]int) int {
    for i := len(triangle) - 2; i >= 0; i-- {
        for j := 0; j < len(triangle[i]); j++ {
            triangle[i][j] += min(triangle[i + 1][j], triangle[i + 1][j + 1])
        }
    }
    return triangle[0][0]
}
func min(a, b int) int{
    if a < b {
        return a
    }
    return b
}