Share my c++ DP solution

  • 0

    The idea is same as House Robber II (dp[n] = max(dp[n+1], dp[n+2]+v[n] ). When you decide whether you rob a house, you need its child solution and child's child solution. res[0] is root's solution, res[1] is root's left child solution, res[2] is root's right child solution. DP function is res[0] = max(L[0]+R[0],L[1]+L[2]+R[1]+R[2]+now->val);

    class Solution {
        vector<int> dp(TreeNode* now)
            vector<int> res(3);
                return res;
            vector<int> L = dp(now->left);
            vector<int> R = dp(now->right);
            res[0] = max(L[0]+R[0],L[1]+L[2]+R[1]+R[2]+now->val);
            res[1] = L[0];
            res[2] = R[0];
            return res;
        int rob(TreeNode* root) {
            vector<int> result = dp(root);
            return result[0];

Log in to reply

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