/**
 * 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<TreeNode*, int>mp;
        return robMemeryDFS(root, mp);
    }
    //考虑一步的记忆化搜索(16 ms): 快了接近100倍
    int robMemeryDFS(TreeNode* root, unordered_map<TreeNode*, int>&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];
    }
};

class Solution {
public:
    int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}, n, m;
    int dfs(int x, int y, vector<vector<int>>& matrix, vector<vector<int>>&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<vector<int>>& matrix) {
        if(matrix.size() == 0) return 0;
        n = matrix.size(), m = matrix[0].size();
        int ans = 0;
        vector<vector<int>>steps(n, vector<int>(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;
    }
};