动态规划，三角形的最大路径和

三角形的最大路径和

#include <string>
#include <iostream>
#include <cctype>
#include <algorithm>
#include <vector>
#include <unordered_map>
#include <cstring>
#include <set>
#include <climits>
using namespace std;
class Solution {
public:
    int getRes(vector<vector<int>>& matrix) {
        int n = matrix.size(); // 总行数
		if (!n) return 0;

        vector<int> Notes(n + 1);
        for (int j = 0; j < n; ++j)
            Notes[j] = matrix[n - 1][j];

        for (int i = n - 2; i >= 0; --i) {
            for (int j = 0; j <= i; ++j) {
                Notes[j] = max(Notes[j], Notes[j + 1]) + matrix[i][j];
            }
        }
        return Notes[0];
    }
};

int main() {
   Solution s;
   vector<vector<int>> matrix = {{2}, {3, 4}, {6, 5, 7}, {4, 1, 8, 3}};
   cout << s.getRes(matrix) << endl;
   return 0;
}