数字金字塔

题目：

有一个金字塔，想从金字塔底走到塔顶。每一条路所花的时间都不一样长。请找出登上金字塔最快的路(所费时间为路径上数字的总和)。每个向上的路径只有左上和右上的两条路。
输入:[[45],[20,33],[34,18,30],[14,45,09,11]]，输出:92

思路：

arr表示输入的二维数组，定义dp[i][j]表示从塔底走到位置(i,j)花费的最少时间。则dp[i][j]=min(dp[i+1][j],dp[i+1][j+1])+arr[i][j],边界条件dp[arr.size()-1][k] = arr[arr.size()-1][k],0<=k<=arr.size()-1 计算顺序为从二维数组的底部向上。

代码：

#include <vector>
using namespace std;
class MinPath {
public:
    int minPathPyramid(vector<vector<int>>& pyramid) {
        for(int i = pyramid.size()-2;i >= 0;i--) {
            for(int j = 0;j <= i;j++) {
                pyramid[i][j] = min(pyramid[i+1][j],pyramid[i+1][j+1]) + pyramid[i][j];
            }
        }
        return pyramid[0][0];
    }
};