LeetCode -- Triangle

LeetCode -- Triangle

題目描述：


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;
    }




}