leetcode:Triangle

leetcode:Triangle

一、 題目

[

[2],

[3,4],

[6,5,7],

[4,1,8,3]

]

如圖，在一個三角形二維數組中有一系列數，求出從頂層到底層最小和的路徑。

二、 分析

思路1遞歸解決，求以某個數為起點的最小和，可以先求出以跟它相鄰的下一層的兩個數為起點的最小和，然後取兩者的更小者，最後與該數相加即可。不過此方法超時

//遞歸，超時 
class Solution {
public:
    int minimumTotal(vector > &triangle) {
       return minimumTotal(triangle,0,0);
    }
    int minimumTotal(vector > &triangle,int row,int col) {
       if(row == triangle.size()-1)
       	  return triangle[row][col];
       return min(minimumTotal(triangle,row+1,col),minimumTotal(triangle,row+1,col+1))+ triangle[row][col]; 
    }
};

思路2 很明顯是動態規劃的題目，求一個三角形二維數組從頂到低端的最小路徑和。維護到某一個元素的最小路徑和，那麼在某一個元素i，j的最小路徑和就是它上層對應的相鄰兩個元素的最小路徑和加上自己的值，遞推式是ans[i][j]=min(ans[i-1][j-1],ans[i-1][j])+triangle[i][j]。最後掃描一遍最後一層的路徑和，取出最小的即可。每個元素需要維護一次，總共有1+2+...+n=n*(n+1)/2個元素，時間復雜度是O(n^2)。而空間上每次只需維護一層即可（因為當前層只用到上一層的元素），所以空間復雜度是O(n)。

class Solution {
public:
    int minimumTotal(vector > &triangle) {
        int len =  triangle.size();
        if(len == 0)
        	return 0;
        if(len == 1)
        	return triangle[0][0];
        int ans[len];
        ans[0] = triangle[0][0];
        
        for(int i=1;i=1;j--)
        		ans[j] = min(ans[j],ans[j-1]) + triangle[i][j];
        
         ans[0] = ans[0] + triangle[i][0]; 
        }
        int minLen = ans[0];
        for(int i=1;i




   思路3換個角度考慮，如果這道題不自頂向下進行動態規劃，而是放過來自底向上來規劃，遞歸式只是變成下一層對應的相鄰兩個元素的最小路徑和加上自己的值，原理和上面的方法是相同的，這樣考慮到優勢在於不需要最後對於所有路徑找最小的，而且第一個元素和最後元素也不需要單獨處理。
class Solution {
public:
    int minimumTotal(vector > &triangle) {
        int len = triangle.size();
        if(len == 0)
			return 0;
		//vector ans(len);//效果一樣 
		int ans[len];
		//把最底層初始 
		for(int i=0;i=0;i--){
			for(int j=0;j<=i;j++){
				ans[j] = min(ans[j],ans[j+1])+triangle[i][j];
			}
		} 
		return ans[0];
    }
};