lintcode-디지털 삼각형 - 109

954 단어
숫자 삼각형을 지정하고 맨 위에서 끝까지 가장 작은 경로와한 걸음 한 걸음 아래 줄의 인접한 숫자로 이동할 수 있다.
예제
예를 들어, 다음 숫자 삼각형을 지정합니다.
[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
상단에서 하단까지의 최소 경로 및 11(2 + 3 + 5 + 1 = 11)
class Solution {
public:
   
    vector<vector<int> > dp;   
    int solve(vector<vector<int> >&v,int i,int j,int n){
        if(dp[i][j]!=INT_MIN)
            return dp[i][j];
        return dp[i][j]=v[i][j]+(i==n?0:min(solve(v,i+1,j,n),solve(v,i+1,j+1,n)));    
    } 
    int minimumTotal(vector<vector<int> > &triangle) {
        const int n=triangle.size();
        const int m=triangle[n-1].size();
        
        for(int i=0;i<n;++i){
            vector<int> base;
            for(int j=0;j<m;++j)
                base.push_back(INT_MIN);
            dp.push_back(base);    
        }
        solve(triangle,0,0,n-1);
    }
};

좋은 웹페이지 즐겨찾기