LeetCodeデジタル三角形の最小パスと問題

タイトルの説明:
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.
 
上記三角形
2
3  4
6  5  7
4  1  8  3
これは動的計画のテーマで、上から下へ、このデジタル三角形の最小経路とを求めて、次の層はこのデジタルに隣接する数字しか選択できなくて、上述の最適解2+3+5+1=11.解く過程で配列境界問題を処理する.
状態遷移方程式の決定:
現在の最小パスと前のレイヤに隣接する2つの数だけで決定されるため、a[i][j]の値がa[0][0]からa[i][j]までの最小パス和として表される.では、次のように表すことができます.
     a[i][j] += min(a[i-1][j],a[i-1][j-1]);
j=0とj=i(現在の行の最初の列と最後の列)を処理する必要があります.

class Solution {
public:
    int minimumTotal(vector > &triangle){
        int n = triangle.size();
        for(int i = 1; i < n; i++)
        {
            for(int j = 0; j <= i; j++) 
            {
                if(j == 0)                        //j    
                    triangle[i][j] += triangle[i-1][j]; 
                else if(j == i)                    //        
                    triangle[i][j] += triangle[i-1][j-1];
                else
                {
                    if(triangle[i-1][j]

方法2:下から上へ
a[i][j] += min(a[i+1][j],a[i+1][j+1]);

class Solution {
	public:
    int minimumTotal(vector > &triangle) 
	{
		for(int i = triangle.size()-2; i >= 0; --i)		//i         
			for(int j = 0; j <= i; ++j)
			{
				if(triangle[i+1][j+1]>triangle[i+1][j])		
                	triangle[i][j] += triangle[i+1][j];
           		else
               	 	triangle[i][j] += triangle[i+1][j+1];
        	}
   		 return triangle[0][0];
    }
};