内容简介:动态规划题第二天
2 0 1 9 -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
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- 解析 :跻身数据科学领域的五条职业规划道路
- Leetcode动态规划之PHP解析(70. Climbing Stairs)
- Leetcode动态规划之PHP解析(72. Edit Distance)
- Leetcode动态规划之PHP解析(152. Maximum Product Subarray)
- Leetcode动态规划之PHP解析(300. Longest Increasing Subsequence)
- Leetcode动态规划之PHP解析(123. Best Time to Buy and Sell Stock III)
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
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》 这本书的介绍吧!