Triangle

   dp:

 int minimumTotal(vector<vector<int> > &triangle) {
        int row=triangle.size();
        vector<int> dp(row+1,INT_MAX);
          dp[1]=triangle[0][0];
        for(int j=1;j<row;j++){
            for(int i=j+1;i>=1;i--){
                dp[i]=min(dp[i],dp[i-1])+triangle[j][i-1];
            }
        }
        int amin=dp[0];
        for(int i=1;i<=row;i++)
            if(amin>dp[i])
                amin=dp[i];
        return amin;       
    }

换个角度考虑一下，如果这道题不自顶向下进行动态规划，而是放过来自底向上来规划，递归式只是变成下一层对应的相邻两个元素的最小路径和加上自己的值，原理和上面的方法是相同的
    int minimumTotal(vector<vector<int> > &triangle) {
        int N = triangle.size();
        vector<int> dp(N,0);
        for (int i = 0; i < N; ++i)
            dp[i] = triangle[N-1][i];
        for (int i = N - 2; i >= 0; --i)
            for (int j = 0; j <= i; ++j)
                dp[j] = triangle[i][j] + min(dp[j], dp[j+1]);

        return dp[0];
    }