给出一个三角形计算从三角形顶部到底部的最小路径和每一步都可以移动到下面一行相邻的数字例如给出的三角形如下[↵ [2],↵ [3,4],↵ [6,5,7],↵ [4,1,8,3]↵]最小的从顶部到底部的路径和是2 3 5 1 11。注意如果你能只用ON的额外的空间来完成这项工作的话就可以得到附加分其中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;
)
)
