🍎 Maximum Fruits Collected || Easy-to-Follow DP Solution 🍇
\uD83C\uDFAF The Crux: Understand This, and You\'re Done! \uD83E\uDDE9\n### Each child can make exactly n-1 moves. If you get this, the problem is as good as so
# \uD83C\uDFAF The Crux: Understand This, and You\'re Done! \uD83E\uDDE9\n### Each child can make exactly `n-1` moves. If you get this, the problem is as good as solved! \uD83D\uDE80\n\n\n```\nclass Solution {\npublic:\n    int dp[1001][1001];\n    int recur(int i,int j,vector<vector<int>>&fruits,int movesLeft, vector<vector<int>>&done,int n){\n\n        if(i<0 or j<0 or i>=n or j>=n) return -1e9;\n        if(movesLeft == 0){\n            if(i==n-1 and j == n-1) return 0;\n            return -1e9;\n        }\n        if(dp[i][j] != -1) return dp[i][j];\n\n        int op1 = fruits[i][j] + recur(i-1,j+1,fruits,movesLeft-1,done,n);\n        int op2 = fruits[i][j] + recur(i,j+1,fruits,movesLeft-1,done,n);\n        int op3 = fruits[i][j] + recur(i+1,j+1,fruits,movesLeft-1,done,n);\n        return dp[i][j] = max({op1,op2,op3});\n    }\n\n    int recur1(int i,int j,vector<vector<int>>&fruits,int movesLeft, vector<vector<int>>&done,int n){\n\t\n        if(i<0 or j<0 or i>=n or j>=n) return -1e9;\n\n        if(i==n-1 and j==n-1){\n            if(movesLeft == 0) return 0;\n            return -1e9;\n        }\n\t\t\n        if(movesLeft == 0){\n            if(i==n-1 and j == n-1) return 0;\n            return -1e9;\n        }\n\n        if(dp[i][j] != -1){\n            return dp[i][j];\n        }\n      \n        int op1 = fruits[i][j] + recur1(i+1,j-1,fruits,movesLeft-1,done,n);\n        int op2 = fruits[i][j] + recur1(i+1,j,fruits,movesLeft-1,done,n);\n        int op3 = fruits[i][j] + recur1(i+1,j+1,fruits,movesLeft-1,done,n);\n       \n        return dp[i][j] = max({op1,op2,op3});\n    }\n    int maxCollectedFruits(vector<vector<int>>& fruits) {\n\n        int n = fruits.size();\n        vector<vector<int>>done(n,vector<int>(n,0));\n\n        int ans = 0;\n        for(int i=0;i<n;i++){\n            ans += fruits[i][i];\n            fruits[i][i] = 0;\n            done[i][i] = 1;\n        }\n        memset(dp,-1,sizeof dp);\n        int op1 = recur(n-1,0,fruits,n-1,done,n);\n        int i,j;\n        memset(dp,-1,sizeof dp);\n        int op2 = recur1(0,n-1,fruits,n-1,done,n);\n\n        return ans + op1 + op2;\n    }\n};\n```
['Dynamic Programming', 'C', 'C++']