# Leetcode 120. Triangle
###### tags: `Leetcode(C++)`

題目 : https://leetcode.com/problems/triangle/ 。

想法 :

跟931題一樣，只是換成三角形與兩個方向而已。

時間複雜度 : O(r*c)。

程式碼 :

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int r=triangle.size(), ans[210][210]={0}, ansi=INT_MAX, dir[2]={-1, 0};
        
        for(int i=0 ; i<r ; i++){
            for(int j=0 ; j<=i ; j++){
                ans[i][j]=INT_MAX;
            }
        }
        
        ans[0][0]=triangle[0][0];
        
        for(int i=1 ; i<r ; i++){
            for(int j=0 ; j<=i ; j++){
                int c1=j+dir[0], c2=j+dir[1];
                
                //cout << i << " " << j << " : " << c1 << " " << c2 << endl;
                
                if(c1 >= 0 && c1 <= i-1){
                    ans[i][j]=min(ans[i][j], ans[i-1][c1]);    
                }
                
                if(c2 >=0 && c2 <= i-1){
                    ans[i][j]=min(ans[i][j], ans[i-1][c2]);    
                }
                
                //cout << ans[i][j] << endl;
                ans[i][j]+=triangle[i][j];
            }
        }
        
        /*for(int i=0 ; i<r ; i++){
            for(int j=0 ; j<=i ; j++){
                printf(" %2d",ans[i][j]);
            }
            cout << endl;
        }*/
        
        for(int i=0 ; i<triangle[r-1].size() ; i++){
            ansi=min(ansi,ans[r-1][i]);
        }
        
        return ansi;
    }
};