题目描述：
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 is 11 (i.e., 2 + 3 + 5 + 1 = 11).
求三角形从上到下构成最小值的和的路径。
思路：
1.使用一个辅助的二维数组保存当前[i,j]的最小和，再遍历一次最后一层的值从而得到最小值。
2.在求和过程中，区分收尾字符和中间字符的情况。
假设arr[i,j]来保留第i行第j列的最小和。则：
arr[0,0] = triangle[0,0];
当j为中间元素：
arr[i,j] = Min(arr[i-1,j], arr[i-1,j-1]) + triangle[i,j]
当j为首元素：
arr[i,0] = arr[i-1,0] + triangle[i,0]
当j为末尾元素：
arr[i,count-1] = arr[i-1,count-2] + triangle[i,count-1]
实现代码：
public class Solution {
public int MinimumTotal(IList
> triangle)
{
if(triangle.Count == 0){
return 0;
}
if(triangle.Count == 1){
return triangle[0][0];
}
var arr = new int[triangle.Count, triangle[triangle.Count - 1].Count];
arr[0,0] = triangle[0][0];
for(var i = 1;i < triangle.Count; i++)
{
var current = triangle[i];
arr[i,0] = current[0] + arr[i-1,0];
for(var j = 1;j < current.Count - 1; j++)
{
arr[i,j] = current[j] + Math.Min(arr[i-1,j],arr[i-1,j-1]);
}
arr[i,current.Count-1] = current[current.Count-1] + arr[i-1,current.Count-2];
}
var len = arr.GetLength(1);
var min = arr[len - 1,0];
for(var i = 1;i < len; i++){
if(min > arr[len - 1,i]){
min = arr[len - 1,i];
}
}
return min;
}
}
?
|