从如何解决子问题着手设计:
考虑当前节点,最大收益由两个子节点决定。
是怎么决定的呢,为解决这个问题,需要保留两种子问题的解来进行规划。;
当前节点的最大收益:
- 取当前节点:一定不能取两个子节点情况的收益和
- 不取当前节点:子节点所有情况的最大收益和
-
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> treeDP(TreeNode* cur) {
if (!cur) {
return vector<int>{0, 0};
}
vector<int> v1 = treeDP(cur->left), v2 = treeDP(cur->right);
vector<int> ret(2);
ret[0] = max(v1[0], v1[1]) + max(v2[0], v2[1]);
ret[1] = v1[0] + v2[0] + cur->val;
return ret;
}
int rob(TreeNode* root) {
vector<int> v = treeDP(root);
return *max_element(v.begin(), v.end());
}
};