打家劫舍(三)

题意

给定一个数字二叉树，不能选相邻的两个节点，问选的数的最大的和是多大

方法

深搜(TLE)

分析

我们递归搜索，每次递归时传递当前位置是否可选

如果不选这个位置，那么下一层递归的点都是可选

如果可选且选定这个位置，那么下一层递归的值都不可选

在递归过程中记录选择的和

最后输出和中的最大值

代码

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    int dfs(TreeNode* r,bool pick = true){ // 当前是否可选
        if(r == NULL)return 0;
        // 当前不选
        int ans = dfs(r->left) + dfs(r->right);
        // 选择当前
        if(pick){
            ans = max(ans, r->val + dfs(r->left,false) + dfs(r->right,false));
        }
        return ans;
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    int rob(TreeNode* root) {
        return dfs(root);
    }
};

复杂度分析

时间复杂度: 最坏情况，每个节点两种分叉，相当于尝试了所有组合，所以总时间复杂度为$O(2^n)O(2^n)$

空间复杂度: 主要和递归深度相关，递归深度不超过树的高度，所以空间复杂度为$O(n)O(n)$

记忆化搜索

分析

上面的方案，在于对于下层的结果，同样的内容反复计算

如果能把下面的结果保存下来，减少重复计算，那么每个节点的计算次数就变成常数次了

考虑用节点的指针和选择状态做为键来记录结果

样例

以样例数据为例

所以最后输出结果即可

代码

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    int dfs(map<pair<TreeNode*,int>,int >& state,TreeNode* r,bool pick = true){ // 当前是否可选
        if(r == NULL)return 0;
        if(state.count({r,pick})) return state[{r,pick}]; //  计算过 不重复计算直接返回结果
        // 当前不选
        int ans = dfs(state,r->left) + dfs(state, r->right); // 递归下降
        // 选择当前
        if(pick){
            ans = max(ans, r->val + dfs(state, r->left,false) + dfs(state, r->right,false)); // 递归下降
        }
        return state[{r,pick}] = ans; // 记录结果并返回
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    int rob(TreeNode* root) {
        map<pair<TreeNode*,int>,int > state = {}; // 状态记录, 键为 节点和选择状态
        return dfs(state, root);
    }
};

复杂度分析

空间复杂度: 主要是设计的状态的值的保存，所以空间复杂度为$O(n)O(n)$

时间复杂度: 每个状态的计算都是常数代价，所以总时间复杂度为$O(n)O(n)$