《leetcode-php》求三角形的最小加权路径和

给出一个三角形，计算从三角形顶部到底部的最小路径和，每一步都可以移动到下面一行相邻的数字，
例如，给出的三角形如下：
[↵ [2],↵ [3,4],↵ [6,5,7],↵ [4,1,8,3]↵]
最小的从顶部到底部的路径和是2 + 3 + 5 + 1 = 11。注意：
如果你能只用O（N）的额外的空间来完成这项工作的话，就可以得到附加分，其中N是三角形中的行总数。
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
For example, given the following triangle
[↵ [2],↵ [3,4],↵ [6,5,7],↵ [4,1,8,3]↵]↵
The minimum path sum from top to bottom is11(i.e., 2 + 3 + 5 + 1 = 11).
Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

<?php /** * @param $arrTriangle * 每个节点的最小$arrMin */ function minimumTotal($arrTriangle) { $num = count($arrTriangle); $arrMin = array(); //先从最下面一层开始 for ($i = $num - 1; $i >= 0 ;$i --) { //求所有层的最小路径值 foreach ($arrTriangle[$i] as $key => $value) { if ($i == $num - 1) { $arrMin[$i][$key] = $value; continue; } $arrMin[$i][$key] = $value + min($arrMin[$i + 1][$key],$arrMin[$i + 1][$key + 1]); } } return $arrMin[0][0]; } $arr=[ [2], [3,4], [6,5,7], [4,1,8,3], ]; $ret = minimumTotal($arr); print $ret;

需要减少额外空间的使用，可以使用传进来的数组。

<?php /** * @param $arrTriangle * 每个节点的最小用入参数组存储 */ function minimumTotal($arrTriangle) { $num = count($arrTriangle); //先从最下面第二层开始,第一层的最小就是自身 for ($i = $num - 2; $i >= 0 ;$i --) { //求所有层的最小路径值 foreach ($arrTriangle[$i] as $key => $value) { $arrTriangle[$i][$key] = $value + min($arrTriangle[$i + 1][$key],$arrTriangle[$i + 1][$key + 1]); } } return $arrTriangle[0][0]; } $arr=[ [2], [3,4], [6,5,7], [4,1,8,3], ]; $ret = minimumTotal($arr); print $ret;