EASY CPP SOLUTION
EASY CPP SOLUTION\n# Intuition\n Describe your first thoughts on how to solve this problem. \n\n\n# Approach\n Describe your approach to solving the problem. \n
**EASY CPP SOLUTION**\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nfor 0,0 iterate diagonally and mark 0 for that room and compute sum\nfor 0,n-1 and n-1,0 \n ---> start from n-1,n-1 and check for its possible direction and take max of it\n      here i am going from bottom to top ,so just reverse the directions\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n^2)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n^2)\n# Code\n```cpp []\nclass Solution {\npublic:\n    int f(int r,int c,int count,vector<vector<int>> &fruits,vector<vector<int>> &dp,int size)\n    {\n        if(count==0)\n        {\n            //if it is the final pos, return its value\n            if(r==0 && c==size-1) return fruits[r][c];\n            return -1;\n        }\n        if(dp[r][c]!=-1) return dp[r][c];\n        int e=-1;\n        //checking for all 3 possible dir \n        if(r-1>=0)\n        {\n            e=f(r-1,c,count-1,fruits,dp,size);\n        }\n        int g=-1;\n        if(r-1>=0 && c+1<size)\n        {\n            g=f(r-1,c+1,count-1,fruits,dp,size);\n        }\n        int h=-1;\n        if(r-1>=0 && c-1>=0)\n        {\n            h=f(r-1,c-1,count-1,fruits,dp,size);\n        }\n\n        if(e==-1 && h==-1 && g==-1) return dp[r][c]=-1e9;\n        //taking max from all all the 3 values\n        dp[r][c]=fruits[r][c]+max({e,g,h});\n        return dp[r][c];\n    }\n    //this f1 is similar to f function\n    int f1(int r,int c,int count,vector<vector<int>> &fruits,vector<vector<int>> &dp,int size)\n    {\n        if(count==0)\n        {\n            //check for pos n-1,0\n            if(r==size-1 && c==0) return fruits[r][c];\n            return -1;\n        }\n        if(dp[r][c]!=-1) return dp[r][c];\n        int e=-1;\n        if(c-1>=0)\n        {\n            e=f1(r,c-1,count-1,fruits,dp,size);\n        }\n        int g=-1;\n        if(r+1<size && c-1>=0)\n        {\n            g=f1(r+1,c-1,count-1,fruits,dp,size);\n        }\n        int h=-1;\n        if(r-1>=0 && c-1>=0)\n        {\n            h=f1(r-1,c-1,count-1,fruits,dp,size);\n        }\n        if(e==-1 && h==-1 && g==-1) return dp[r][c]=-1e9;\n        dp[r][c]=fruits[r][c]+max({e,g,h});\n        return dp[r][c];\n    }\n    int maxCollectedFruits(vector<vector<int>>& fruits) {\n        int n=fruits.size();\n        int sum=0;\n        int r=0;\n        int c=0;\n        while(r<n && c<n)\n        {\n            sum+=fruits[r][c];\n            fruits[r][c]=0;\n            r++;\n            c++;\n        }\n        vector<vector<int>> dp(n,vector<int>(n,-1));\n        vector<vector<int>> dp1(n,vector<int>(n,-1));\n        //it will cal max for 0,n-1\n        sum+=f(n-1,n-1,n-1,fruits,dp,n);\n        //it will cal max for n-1,0\n        sum+=f1(n-1,n-1,n-1,fruits,dp1,n);\n        return sum;\n    }\n};\n```
['Dynamic Programming', 'Memoization', 'C++']