2019-05-18 吴亲库里 库里的深夜食堂
给定一个三角形，好吧，其实就是一个二维数组，让我们求从上至下的最小路径和，往下一层，你只能移动相邻之间的两个数。
还是使用动态规划的两个步骤。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];
}
