Disk Stacking

• Time : O(n^2)
• Space : O(n)

#include <vector>
using namespace std;

int helper(vector<vector<int>>& d, vector<int>& dp, vector<int>& path, int p) {
    if(dp[p] != -1) return dp[p];
    int n = d.size();
    int& res = dp[p] = d[p][2];
    for(int i = 0; i < n; i++) {
        if(d[i][0] >= d[p][0] or d[i][1] >= d[p][1] or d[i][2] >= d[p][2]) continue;
        int h = d[p][2] + helper(d, dp, path, i);
        if(h > res) {
            res = h;
            path[p] = i;
        }
    }
    return res;
}

vector<vector<int>> diskStacking(vector<vector<int>> disks) {
    int n = disks.size(), ma = 0, root = -1;
    vector<int> dp(n, -1), path(n, -1);
    for(int i = 0; i < n; i++) {
        if(helper(disks, dp, path, i) > ma) {
            ma = dp[i];
            root = i;
        }
    }
    vector<vector<int>> res;
    while(root != -1) {
        res.push_back(disks[root]);
        root = path[root];
    }
	reverse(begin(res), end(res));
    return res;
}