/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public://递归程序就是结构演绎，有点像dp，只要定义好每一次递归过程完成的是同一个目标，就能保证所有递归结束之后完成的效果是最终的目标    int rob_naive(TreeNode* root) {
   // 返回当前节点开始的能够rob的最大值。        if(root == NULL) return 0;//当前节点为空 0        int val = 0;        if(root -> left)//左孩子不空            val += rob(root -> left -> left) + rob(root -> left -> right); //rob当前root 和 root 的孩子的孩子的能rob到的最大值。这里并不是rob孩子的孩子，而是孩子的孩子能rob的最大值就像这个递归结构每一次完成的目标一样。        if(root -> right)            val += rob(root -> right -> left) + rob(root -> right -> right);        return max(val + root -> val, rob(root -> left) + rob(root -> right));        //返回 rob(root, root's children 's children   or   root's children)    }    //看上面的方案(1330 ms)：每一次我们都考虑了 root.left.left & root.left.right & root.right.left & root.right.right                                    // root.left & root.right 这里在递归计算的时候还是会算到上面计算过的值。                                    //所以给出一个考虑一步之后的优化记忆搜索。    int rob(TreeNode* root){        unordered_map
     
      mp;        return robMemeryDFS(root, mp);    }    //考虑一步的记忆化搜索(16 ms): 快了接近100倍    int robMemeryDFS(TreeNode* root, unordered_map
      
       &mp){        if(root == NULL) return 0;        if(mp[root]) return mp[root];        int val = 0;        if(root -> left)//左孩子不空            val += robMemeryDFS(root -> left -> left, mp) + robMemeryDFS(root -> left -> right, mp);        if(root -> right)            val += robMemeryDFS(root -> right -> left, mp) + robMemeryDFS(root -> right -> right, mp);        mp[root] = max(val + root -> val, robMemeryDFS(root -> left, mp) + robMemeryDFS(root -> right, mp));        return mp[root];    }};
      
     

 附加一道 同样使用记忆化搜索的题目 329. Longest Increasing Path in a Matrix

class Solution {public:    int dir[4][2] = {
   {
   1, 0}, {-1, 0}, {
   0, 1}, {
   0, -1}}, n, m;    int dfs(int x, int y, vector
     
      
       >& matrix, vector
       
        
         >&steps){        if(steps[x][y]) return steps[x][y];        int maxSteps = 0; // record the longest path steps from (x, y)        for(int i = 0; i < 4; i ++){            int nx = dir[i][0] + x, ny = dir[i][1] + y, tmp = 0;            if(nx >= 0 && ny >= 0 && nx < n && ny < m && matrix[nx][ny] > matrix[x][y]){                maxSteps = max(maxSteps, dfs(nx, ny, matrix, steps));            }        }        steps[x][y] = maxSteps + 1; // + 1 for cur(x, y)        return steps[x][y];    }    int longestIncreasingPath(vector
         
          
           >& matrix) { if(matrix.size() == 0) return 0; n = matrix.size(), m = matrix[0].size(); int ans = 0; vector
           
            
             >steps(n, vector
             
              (m, 0)); for(int i = 0; i < n; i ++) for(int j = 0; j < m; j ++) ans = max(ans, dfs(i, j, matrix, steps)); return ans; }};