Skip to content

Instantly share code, notes, and snippets.

@edman
Created April 5, 2016 17:36
Show Gist options
  • Save edman/b903e06e3362abe1e7df201f1468aaf2 to your computer and use it in GitHub Desktop.
Save edman/b903e06e3362abe1e7df201f1468aaf2 to your computer and use it in GitHub Desktop.
House Robber III dynamiic programming memoization with tree payloads
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
struct Payload {
int dk, dkb;
};
void compute(TreeNode *n, Payload *p) {
Payload *pl = 0, *pr = 0;
TreeNode *nl = n->left, *nr = n->right;
if (nl) pl = new Payload(), compute(nl, pl);
if (nr) pr = new Payload(), compute(nr, pr);
p->dk = n->val + (pl ? pl->dkb : 0) + (pr ? pr->dkb : 0);
p->dkb = (pl ? max( pl->dk, pl->dkb ) : 0) + (pr ? max( pr->dk, pr->dkb ) : 0);
if (pl) delete pl;
if (pr) delete pr;
}
int rob(TreeNode* root) {
if (!root) return 0;
Payload *proot = new Payload();
compute(root, proot);
return max(proot->dk, proot->dkb);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment