BEATS 100% || Java Solution || Optimum Solution
Intuition\n- The problem involves collecting the maximum number of fruits from a grid, where each cell contains a specific number of fruits. We need to navigate
# Intuition\n- The problem involves collecting the maximum number of fruits from a grid, where each cell contains a specific number of fruits. We need to navigate the grid and collect as many fruits as possible, following certain movement rules or constraints. The goal is to use dynamic programming (DP) to track the maximum fruits collected at each step.\n\n# Approach\n- **Dynamic Programming (DP) Table :**\n  - Create a DP table dp where dp[i][j] represents the maximum fruits collected when reaching cell (i, j).\n\n- **Initialization :**\n  - Initialize the DP table with appropriate starting values. For instance, the top-right and bottom-left corners are initialized based on the given fruits.\n\n- **Filling the DP Table :**\n  - Iterate over the grid and update the DP table based on previous values, considering the allowed moves (right, down, etc.).\n\n- **Combining Results :**\n  - Combine the results from different paths to get the final maximum number of fruits collected.\n\n# Complexity\n- Time complexity: `O(n^2)`\n\n- Space complexity: `O(n^2)`\n\n# Code\n```java []\nclass Solution {\n    int max(int a, int b) {\n        return a > b ? a : b;\n    }\n    public int maxCollectedFruits(int[][] fruits) {\n        int n = fruits.length;\n        int[][] dp = new int[n][n];\n        dp[0][n-1] = fruits[0][n-1];\n        for(int i=0; i<n-1; i++){\n            dp[0][i] = -99999999;\n        }\n        for(int i=1; i<n-1; i++){\n            for(int j=n-i-1; j<n; j++){\n                dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]);\n                if(j < n-1){\n                    dp[i][j] = max(dp[i-1][j+1], dp[i][j]);\n                }\n                dp[i][j] += fruits[i][j];\n            }\n        }\n        int ret = dp[n-2][n-1];\n       dp[n-1][0] = fruits[n-1][0];\n        for(int i=0; i<n-1; i++){\n            dp[i][0] = -99999999;\n        }\n        for(int i=1; i<n-1; i++){\n            for(int j=n-i-1; j<n; j++){\n                dp[j][i] = max(dp[j][i-1], dp[j-1][i-1]);\n                if(j < n-1) {\n                    dp[j][i] = max(dp[j+1][i-1], dp[j][i]);\n                }\n                dp[j][i] += fruits[j][i];\n            }\n        }        \n        ret += dp[n-1][n-2];\n        for(int i=0; i<n; i++){\n            ret += fruits[i][i];\n        }\n        return ret;\n    }\n    \n}\n```
['Array', 'Dynamic Programming', 'Greedy', 'Java']