Clean c++ DP solution

  • 1

    maximum benefit involves decision of whether to rob current one or not.

    int rob(TreeNode* root) {
            return rob_help(root).first;
    pair<int, int> rob_help(TreeNode *root) {
            pair<int, int> result(0, 0);
            if (root != NULL) {
                pair<int, int> left = rob_help(root->left);
                pair<int, int> right = rob_help(root->right);
                result.second = left.first + right.first;
                result.first = max(root->val + left.second + right.second, result.second);
            return result;

  • 0

    But this program doesn't neccessarily skip directly linked houses aka nodes?

  • 0

    @JPBlack I maintain result in a pair, first part indicates best benefit no matter whether includes himself, and second part indicates the one without including himself.
    So root->val + left.second + right.second means includes himself but skip all his children.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.