4 Solutions | 3D-DP, 2D-DP
Solution 1 to 3 (3D-DP Recursion->memoization->tabulation):\n Idea is simple - Simulate taking & not taking behavior at each cell.\n\n# Solution-4: (2D-DP):\n A
# Solution 1 to 3 (3D-DP Recursion->memoization->tabulation):\n* Idea is simple - Simulate taking & not taking behavior at each cell.\n\n# Solution-4: (2D-DP):\n* At each cell, you should be able to figure out the smallest possible number till that point (i.e from it\'s left and top side).\n* Consider the current cell as the max item and take diff. Track the result on the way (i.e max diff possible).\n# CODE:\n```\nclass Solution {\n    unordered_map<string, int> dp;\n    vector<vector<int>> grid;\n    vector<vector<vector<int>>> dp1;\npublic:\n    int maxScore(vector<vector<int>>& g) \n    {\n        grid = g;\n        int ans = INT_MIN;\n        if ( isStrictlyIncreasing(grid, ans) )\n            return ans;\n        \n        // SOL-1: RECURSION -- TLE -- 505 / 564 test cases passed. -- 89.53%\n        // return dfs(grid, 0, 0, -1);\n        \n        // SOL-2: MEMOIZATION -- TLE -- 505 / 564 test cases passed. -- 89.53%\n        // return memo(0, 0, -1);\n        \n        // SOL-3: OPtimized Memo -- TLE -- 505 / 564 test cases passed. -- 89.53%\n        // dp1 = vector<vector<vector<int>>>(grid.size()+1, vector<vector<int>>(grid[0].size()+1, vector<int>(1e5+1, -1)));\n        // return memo1(0,0,-1);\n        \n        // SOL-4: 2D DP -- TC: O(m*n), SC: O(1) -- 100% -- All TCs passed.\n        return sol4(g);\n    }\n    \n\t// SOL-4: 2D DP -- TC: O(m*n), SC: O(1) -- 100% -- All TCs passed.\n    int sol4(vector<vector<int>>& grid)\n    {\n        int m = grid.size();\n        int n = grid[0].size();\n        int ans = INT_MIN;\n        \n        for ( int i=0; i<m; i++ )\n        {\n            for ( int j=0; j<n; j++ )\n            {\n                int mn = INT_MAX;\n                if ( i==0 && j==0 ) continue;\n                // top\n                if (i) mn = min(mn, grid[i-1][j]);\n\n                // left\n                if (j) mn = min(mn, grid[i][j-1]);\n                ans = max(ans, grid[i][j] - mn);\n                grid[i][j] = min(grid[i][j], mn);\n            }\n        }\n        return ans;\n    }\n    \n    // SOL-3: OPTIMIZED MEMO -- TLE -- 505 / 564 test cases passed. -- 89.53%\n    int memo1(int i, int j, int prev)\n    {\n        if ( i>=grid.size() || j>=grid[0].size() )\n            return 0;\n        \n        if ( dp1[i][j][prev+1] != -1 )\n            return dp1[i][j][prev+1];\n        \n        // take\n        int ans1 = -1;\n        if ( prev == -1 )\n            ans1 = max(memo(i+1, j, grid[i][j]), memo(i, j+1, grid[i][j]));\n        else\n            ans1 = grid[i][j] - prev + max(memo(i+1, j, grid[i][j]), memo(i, j+1, grid[i][j]));\n        \n        // do not take\n        int ans2 = max(memo(i+1, j, prev), memo(i, j+1, prev));\n        return dp1[i][j][prev+1] = max(ans1, ans2);\n    }\n    \n    // SOL-2: MEMOIZATION -- TLE -- 505 / 564 test cases passed. -- 89.53%\n    int memo(int i, int j, int prev)\n    {\n        if ( i>=grid.size() || j>=grid[0].size() )\n            return 0;\n        \n        string key = to_string(i) + "_" + to_string(j) + "_" + to_string(prev);\n        if ( dp.find(key) != dp.end() )\n            return dp[key];\n        \n        // take\n        int ans1 = -1;\n        if ( prev == -1 )\n            ans1 = max(memo(i+1, j, grid[i][j]), memo(i, j+1, grid[i][j]));\n        else\n            ans1 = grid[i][j] - prev + max(memo(i+1, j, grid[i][j]), memo(i, j+1, grid[i][j]));\n        \n        // do not take\n        int ans2 = max(memo(i+1, j, prev), memo(i, j+1, prev));\n        return dp[key] = max(ans1, ans2);\n    }\n    \n    // SOL-1: RECURSION -- TLE -- 505 / 564 test cases passed. -- 89.53%\n    int dfs(const vector<vector<int>>& grid, int i, int j, int prev)\n    {\n        if ( i>=grid.size() || j>=grid[0].size() )\n            return 0;\n        \n        // take\n        int ans1 = -1;\n        if ( prev == -1 )\n            ans1 = max(dfs(grid, i+1, j, grid[i][j]), dfs(grid,i, j+1, grid[i][j]));\n        else\n            ans1 = grid[i][j] - prev + max(dfs(grid, i+1, j, grid[i][j]), dfs(grid,i, j+1, grid[i][j]));\n        \n        // do not take\n        int ans2 = max(dfs(grid, i+1, j, prev), dfs(grid, i, j+1, prev));\n        return max(ans1, ans2);\n    }\n    \n    // TC: O(m*n + m*n) = O(m*n), SC: O(1).\n    bool isStrictlyIncreasing(const vector<vector<int>>& grid, int &ans)\n    {\n        // validate all rows.\n        for ( int i=0; i<grid.size(); i++ )\n        {\n            unordered_set<int> hs;\n            for ( int j=0; j<grid[i].size(); j++ )\n            {\n                int x = grid[i][j];\n                for ( int num: hs ) {\n                    if ( num <= x )\n                        return false;\n                    ans = max(ans, x-num);\n                }\n                hs.insert(x);\n            }\n        }\n        \n        // validate all columns.\n        for ( int j=0; j<grid[0].size(); j++ )\n        {\n            unordered_set<int> hs;\n            for ( int i=0; i<grid.size(); i++ )\n            {\n                int x = grid[i][j];\n                for ( int num : hs ) {\n                    if ( num <= x )\n                        return false;\n                    ans = max(ans, x-num);\n                }\n                hs.insert(x);\n            }\n        }\n        \n        return true;\n    }\n};\n```
['Dynamic Programming']