我和你一样😂
点赞 评论

相关推荐

12-08 10:19
门头沟学院 C++
打家劫舍三道题:街道题递推公式:dp[i] = max(dp[i-2] + nums[i], dp[i-1])(当前这户偷还是不偷);围城题就要分两种情况去考虑,分别是不含首元素,和不含尾元素,其它和前面一致;二叉树题比较难,如下:vector traversal(TreeNode* cur){        vector dp(2, 0);        //递归出口        if(cur == nullptr) return {0, 0};        //左        vector leftdp = traversal(cur->left);        //右        vector rightdp = traversal(cur->right);        //中        //不偷当前结点,那么就要考虑偷左右孩子结点(不是一定偷,主要是取最大值)        int val1 = max(leftdp[0], leftdp[1]) + max(rightdp[0], rightdp[1]);        //偷当前结点,那么左右孩子结点一定不能偷了 int val2 = cur->val + leftdp[0] + rightdp[0];        return {val1, val2};    }    int rob(TreeNode* root) {        //打家劫舍二叉树        //递归采用后序遍历的方式,因为决定偷不偷当前结点是由左右子节点偷不偷决定的        //定义一个包含两个元素的一维dp数组(每层递归里都有个dp数组)        //dp[0]表示不偷当前结点盗取的最大金额,dp[1]表示偷当前结点盗取的最大金额        //递归函数最后返回的也是一个dp数组,表示偷不偷根节点(所有子节点都遍历完了)        vector result = traversal(root);        return max(result[0], result[1]);    }
点赞 评论 收藏
分享
牛客网
牛客企业服务