Simple observation for dp values
\n\n# Complexity\n- Time complexity:O(nm)\n Add your time complexity here, e.g. O(n) \n\n- Space complexity:O(nm)\n Add your space complexity here, e.g. O(n) \n
\n\n# Complexity\n- Time complexity:O(n*m)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(n*m)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\n\n    int solve1(int r,int c,vector<vector<int>> &dp,vector<vector<int>> &matrix,int n){\n        if(r<0 || r>=n || c<0 || c>=n)\n        return -1e9-1;\n\n        if(c==n-1){\n            if(r==n-1)\n            return matrix[r][c];\n\n            else return -1e9-1;\n\n        }\n\n        if(dp[r][c]!=-1)\n        return dp[r][c];\n\n        int ans=-1e9-1;\n\n        ans=max(ans,matrix[r][c]+solve1(r-1,c+1,dp,matrix,n));\n        ans=max(ans,matrix[r][c]+solve1(r,c+1,dp,matrix,n));\n        ans=max(ans,matrix[r][c]+solve1(r+1,c+1,dp,matrix,n));\n\n        return dp[r][c]=ans;\n    }\n\n    int solve2(int r,int c,vector<vector<int>> &dp,vector<vector<int>> &matrix,int n){\n        if(r<0 || r>=n || c<0 || c>=n)\n        return -1e9-1;\n\n        if(r==n-1){\n            if(c==n-1)\n            return matrix[r][c];\n\n            else return -1e9-1;\n\n        }\n\n        if(dp[r][c]!=-1)\n        return dp[r][c];\n\n        int ans=-1e9-1;\n\n        ans=max(ans,matrix[r][c]+solve2(r+1,c+1,dp,matrix,n));\n        ans=max(ans,matrix[r][c]+solve2(r+1,c,dp,matrix,n));\n        ans=max(ans,matrix[r][c]+solve2(r+1,c-1,dp,matrix,n));\n\n        return dp[r][c]=ans;\n    }\n    int maxCollectedFruits(vector<vector<int>>& fruits) {\n        \n        int ans=0;\n        int n=fruits.size();\n\n        for(int i=0;i<n;i++){\n            for(int j=0;j<n;j++){\n                if(i==j){\n                  ans+=fruits[i][j];\n                }\n                \n            }\n        }\n\n        vector<vector<int>> matrix1(n,vector<int>(n,0)),matrix2(n,vector<int>(n,0));\n\n        for(int i=0;i<n;i++){\n            for(int j=0;j<n;j++){\n                if(i<j)\n                matrix2[i][j]=fruits[i][j];\n                else if(j<i)\n                matrix1[i][j]=fruits[i][j];\n\n\n            }\n        }\n\n        vector<vector<int>> dp1(n,vector<int>(n,-1)),dp2(n,vector<int>(n,-1));\n\n        ans+=solve1(n-1,0,dp1,matrix1,n)+solve2(0,n-1,dp2,matrix2,n);\n\n        return ans;\n    }\n};\n```
['Array', 'Dynamic Programming', 'Matrix', 'C++']