Leetcode动态规划之PHP解析(120. Triangle)

2019-5-18 星期六  开始吧

上一题链接: Leetcode动态规划之PHP解析(70. Climbing Stairs)

动态规划题第二天

题目描述

给定一个三角形，好吧，其实就是一个二维数组，让我们求从上至下的最小路径和，往下一层，你只能移动相邻之间的两个数。

题目解析

还是使用动态规划的两个步骤。1.定义好状态2.求出递推的公式。递归和动态规划有一个不同的地方就是递归是自上而下，比如在这里从上面一层一层的计算调用，到了递归的出口，又一层一层的回来。而动态规划是自下而上进行思考。对于这里状态定义，我们现在是从下往上的概念，当前是一个二维数组。

所以我们可以推出它的递推公式。

我们把路径最短值存在(用坐标来说就是横坐标i,纵坐标j的位置),所以最终只需要返回(0,0)坐标即二维数组$dp[0][0]位置的值即可。

具体实现

     /**
     * @param Integer[][] $triangle
     * @return Integer
     */
    function minimumTotal($triangle) {

     if(empty(count($triangle))){
         return 0;
     }
        for($i=count($triangle)-1;$i>=0;$i--){
            for($j=0;$j<count($triangle[$i]);++$j){
                $triangle[$i][$j] +=min($triangle[$i+1][$j],$triangle[$i+1][$j+1]);
            }
        }
        return $triangle[0][0];
    }

我们也可以把结果存在一个一维数组中。因为我们每次计算的时候并不需要通过所以层的结果，只需要一层的结果就能算出当前层的结果。所以数组的初始值是最后一层，因为最后一层的最小值就是他自己，然后从倒数第二层开始递推。

  /**
     * @param Integer[][] $triangle
     * @return Integer
     */
    function minimumTotal($triangle) {
        if(empty(count($triangle))){
         return 0;
     }
        $res=$triangle[count($triangle)-1];
        for($i=count($triangle)-2;$i>=0;$i--){
            for($j=0;$j<count($triangle[$i]);++$j){
                $res[$j]=$triangle[$i][$j]+min($res[$j],$res[$j+1]);
            }
        }
        return $res[0];
    }

Github整理地址:https://github.com/wuqinqiang/leetcode-php