[C++] Easy Top Down DP - Clean & Concise
Idea\n- Try all possible pair of (r, c) in range [0..n-1] as the center of the axis-aligned plus sign.\n\t- Get the length of 4 arms: RIGHT, DOWN, LEFT, UP\n\t-
**Idea**\n- Try all possible pair of `(r, c)` in range `[0..n-1]` as the center of the **axis-aligned plus sign**.\n\t- Get the length of 4 arms: RIGHT, DOWN, LEFT, UP\n\t- The size of **plus-sign** is the minimum between 4 arms.\n- Choose the sign with have the maximum size.\n- **HOW to get the length of 4 arms efficient?**\n\t- We can use **Dynamic Programming** to calculate the maximum size of 4 arms start with pos `(r, c)` in 4 directions: RIGHT, DOWN, LEFT, UP.\n\t- Let `dp(r, c, d)` is the longest arm start at cell `r, c` and extend in direction `d`. If we define `DIR = [0, 1, 0, -1, 0]`, then:\n\t\t- `d = 0` means RIGHT direction, corresponding to `(r + DIR[0], c + DIR[1])`\n\t\t- `d = 1` means DOWN direction, corresponding to `(r + DIR[1], c + DIR[2])`\n\t\t- `d = 2` means LEFT direction, corresponding to `(r + DIR[2], c + DIR[3])`\n\t\t- `d = 3` means TOP direction, corresponding to `(r + DIR[3], c + DIR[4])`\n\t- Base case: If `(r, c)` is out of bound or `grid[r][c] is a mined cell` then `dp(r, c, d) = 0`.\n\t- Transition state: `dp(r, c, d) = dp(r + DIR[i], c + DIR[i+1], d) + 1`.\n```c++\nclass Solution {\npublic:\n    int orderOfLargestPlusSign(int n, vector<vector<int>>& mines) {\n        vector<vector<bool>> isMine(n, vector<bool>(n, false));\n        for (auto& pos: mines) isMine[pos[0]][pos[1]] = true;\n        int ans = 0;\n        for (int r = 0; r < n; ++r) {\n            for (int c = 0; c < n; ++c) {\n                int plusSignSize = dpMaxArm(n, isMine, r, c, 0);\n                for (int d = 1; d < 4; ++d)\n                    plusSignSize = min(plusSignSize, dpMaxArm(n, isMine, r, c, d));\n                ans = max(ans, plusSignSize);\n            }\n        }\n        return ans;\n    }\n\n    int DIR[5] = {0, 1, 0, -1, 0};\n    int memo[500][500][4] = {};\n    int dpMaxArm(int n, vector<vector<bool>>& isMine, int r, int c, int d) {\n        if (r < 0 or r >= n or c < 0 or c >= n or isMine[r][c]) return 0;\n        if (memo[r][c][d] != 0) return memo[r][c][d];\n        return memo[r][c][d] = dpMaxArm(n, isMine, r + DIR[d], c + DIR[d+1], d) + 1;\n    }\n};\n```\n**Complexity**\n- Time: `O(N^2)`, where `N <= 500` is the side size of the square grid.\n- Space: `O(N^2)`\n\nIf you think this **post is useful**, I\'m happy if you **give a vote**. Any **questions or discussions are welcome!** Thank a lot.
[]