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

栏目: PHP · 发布时间: 5年前

内容简介:动态规划题第二天

2 0 1 9 -5 -18   期六    

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

动态规划题第二天

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

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

题目解析

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

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

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

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

我们把路径最短值存在(用坐标来说就是横坐标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


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

JavaScript: The Definitive Guide, 5th Edition

JavaScript: The Definitive Guide, 5th Edition

David Flanagan / O'Reilly Media / 2006-08-01 / USD 49.99

This Fifth Edition is completely revised and expanded to cover JavaScript as it is used in today's Web 2.0 applications. This book is both an example-driven programmer's guide and a keep-on-your-desk ......一起来看看 《JavaScript: The Definitive Guide, 5th Edition》 这本书的介绍吧!

URL 编码/解码
URL 编码/解码

URL 编码/解码

MD5 加密
MD5 加密

MD5 加密工具

SHA 加密
SHA 加密

SHA 加密工具