Find Maximum Number Of Fruits Collected, C++ Detailed Solution
Do Upvote If Found Helpful !!!\n\n# Approach\nThe problem here is quite interesting and needs some pretty good observations. First of all lets try to understand
***Do Upvote If Found Helpful !!!***\n\n# Approach\nThe problem here is quite interesting and needs some pretty good observations. First of all lets try to understand the problem. So we we have **3 children** : Lets name them as **A, B** and **C**. **A** stands at **(0,0) [Top Left]**, **B** stands at **(0,N-1) [Top Right]** and **C** stands at **(N-1,0) [Bottom Left]**. Now all of them can move following the rules specified for them and they need to reach the the **Bottom Right cell (N-1,N-1)** in exactly **N-1** moves. Along their way, they can pick up fruits. We need to tell the maximum fruits they can collect !\n\nNow the very first approach that strikes the mind is that for each child, perform the movements and try to find the maximum fruits they can collect before reaching the last cell. So this means that we need to get **ANS = Max(A) + Max(B) + Max(C)**, which seems to be fair enough as we are trying to maximise the fruits collected by each person so a greedy approach. But here is the most important thing that we miss out. The above approach would have been correct if the after visiting a cell, **the number of fruits remains same and that everyone who visits that cell can collect fruits** but that is not the case. Once a cell is visited, its fruits are collected and noone else can collect them afterwards. This means that instead of optimising fruits collected by each child, we need to look at collaborative effort of all childern !\n\n\nHere comes the magic that we need ! We need to observe two important points.\n\n**1)** Every child needs to reach the last cell in exactly **N-1** moves. Not longer, not shorter.\n\n**2)** Since each cell has positive values, the maximum fruit collection can be done if all of them try to follow different paths or **non-adjoint** paths (Avoid following same paths again as long as possible).\n\n**3)** Look at the movement of each child. For child **A**, the only possible way for it to each the end cell in N-1 moves is moving through the diagonal. Thus child **A** can only move along the diagonal. For **B**, since we know that child **A** will cover diagonal, we can limit the movement of **B** within the upper half of diagonal. Similarly **C** can cover the lower half below the diagonal. In this way, we ensure that each of **A, B** and **C** will follow **non-overlapping** paths. Its also very obvious to see that none of children will ever explore the upper left half of diagonal. An image below will make the movements more clear.\n\n\n![WhatsApp Image 2024-12-07 at 20.55.04_6340699a.jpg](https://assets.leetcode.com/users/images/b010162d-24c3-4f20-978a-3b59840029b9_1733585172.89083.jpeg)\n\n\n\nNow what do we do ? For child **A** just add up the diagonal values. For **B** run a recursive function that covers the upper half of diagonal. Use **Dynamic Programming** to memoize the overlapping cell states. At last for **C** too run a recursive function that covers lower half of diagonal. Use **DP** for this too. An important thing to note here is that for each child movement is such specified that it never repeats the same cells again in a single way path **(No cyclic paths)**. At the end just add up all 3 values and you have your answer. Below is the given implementation for this problem.\n\n\n# Complexity\n- Time complexity: **O(N^2)**\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: **O(N^2)**\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    vector<vector<int>>dir1 = {{1,1},{-1,1},{0,1}};\n    vector<vector<int>>dir2 = {{1,1},{1,-1},{1,0}};\n\n    int dfs1(vector<vector<int>>& G, int i, int j, int &n, vector<vector<int>>& dp){       // For Lower Half Of Half Grid\n        if(j == n-1){\n            return i == n-1 ? 0 : INT_MIN;\n        }\n        else if(dp[i][j] != -1){\n            return dp[i][j];\n        }\n        int ans = INT_MIN;\n        for(int k = 0; k < 3; k++){\n            int dx = i + dir1[k][0], dy = j + dir1[k][1];\n            if(dx >= 0 && dy >= 0 && dx < n && dy < n && dx >= dy){\n                int val = dfs1(G, dx, dy, n, dp);\n                if(val != INT_MIN){\n                    val += (G[dx][dy] * ((dx == dy) ? 0 : 1));\n                }\n                ans = max(ans, val);\n            }\n        }\n        return dp[i][j] = ans;\n    }\n\n    int dfs2(vector<vector<int>>& G, int i, int j, int &n, vector<vector<int>>& dp){                    // For upper half of half grid\n        if(i == n-1){\n            return j == n-1 ? 0 : INT_MIN;\n        }\n        else if(dp[i][j] != -1){\n            return dp[i][j];\n        }\n        int ans = INT_MIN;\n        for(int k = 0; k < 3; k++){\n            int dx = i + dir2[k][0], dy = j + dir2[k][1];\n            if(dx >= 0 && dy >= 0 && dx < n && dy < n && dx <= dy){\n                int val = dfs2(G, dx, dy, n, dp);\n                if(val != INT_MIN){\n                    val += (G[dx][dy] * ((dx == dy) ? 0 : 1));\n                }\n                ans = max(ans, val);\n            }\n        }\n        return dp[i][j] = ans;\n    }\n\n    int maxCollectedFruits(vector<vector<int>>& fruits) {\n        int n = fruits.size(), ans = 0;\n        for(int i = 0; i < n; i++){\n            ans += fruits[i][i];\n        }\n        vector<vector<int>>dpr(n,vector<int>(n,-1)), dpc(n,vector<int>(n,-1));\n        int u = dfs1(fruits, n-1, 0, n, dpc) + fruits[n-1][0];\n        int v = dfs2(fruits, 0, n-1, n, dpr) + fruits[0][n-1];\n        ans += (u + v);\n        return ans;\n    }\n};\n```
['Math', 'Dynamic Programming', 'Greedy', 'Depth-First Search', 'Graph', 'C++']