C++ || Easy DP || Beats 100% || No Recursion
Intuition\n Describe your first thoughts on how to solve this problem. \n- For child that starts at $(0, 0)$, the only possible path to reach $(n-1, n-1)$ withi
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n- For child that starts at $(0, 0)$, the only possible path to reach $(n-1, n-1)$ within n-1 steps is to go on the main diagonal.\n\n- For children that start at $(0, n-1)$ and $(n-1, 0)$, the only possible paths to reach $(n-1, n-1)$ within n-1 steps is if they never cross past the main diagonal (including it) and past the secondary diagonal (excluding it). \n\n# Conditions\n\nOn the main diagonal, we have cells where $i=j$. Hence:\n- To stay below, we need $i > j$\n- To stay above, we need $i < j$\n\nOn the secondary diagonal, we have cells where $i+j = n-1$. Hence:\n- To stay below, we need $i+j > n-1$\n- To stay above, we need $i+j < n-1$\n\n# DP\nIn my solution, I simulate the path backwards (bottom-up).\n\nSince child $(0, n-1)$ should never be on the main diagonal, his last position before reaching $(n-1, n-1)$ will be $(n-2, n-1)$, so I start the algorithm from here. \n\nSince child $(n-1, 0)$ should never be on the main diagonal, his last position before reaching $(n-1, n-1)$ will be $(n-1, n-2)$, so I start the algorithm from here.\n\nFor child $(0, n-1$), we can reach position $(i, j)$ from 3 cells: \n- $(i+1, j)$, $(i+1, j-1)$, $(i+1, j)$ \n\nFor child $(n-1, 0)$, we can reach position $(i, j)$ from 3 cells:\n- $(i, j+1)$, $(i-1, j+1)$, $(i-1, j)$\n\n\n\n \n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int maxCollectedFruits(vector<vector<int>>& fruits) {\n        // child starting from (0, 0) can only move diagonally;\n        int totalFruits=0, n=fruits.size();\n        for(int i=0; i<n; i++) // (0,0) contribution\n            totalFruits += fruits[i][i];\n        \n        // kid (0, n-1) should always stay above the main diagonal and below secondary diagonal;\n        vector<vector<int>> dp(n, vector<int>(n, 0));\n\n        dp[n-2][n-1] = fruits[n-2][n-1];\n        for(int i=n-3; i>=0; i--)\n            for(int j=max(i+1, n-i-1); j<n; j++) {\n                // check (i+1, j) if above main diagonal and below secondary diagonal \n                if(i+1 < j && i+j+1 >= n-1) \n                    dp[i][j] = max(dp[i][j], fruits[i][j] + dp[i+1][j]);\n                // check (i+1, j-1) if above main diagonal and below secondary diagonal\n                if(i+1 < j-1 && i+j >=n-1)\n                    dp[i][j] = max(dp[i][j], fruits[i][j] + dp[i+1][j-1]);\n                // check (i+1, j+1) if above main diagonal and below secondary diagonal\n                if(i < j && i+j+2>= n-1 && j<n-1)\n                    dp[i][j] = max(dp[i][j], fruits[i][j] + dp[i+1][j+1]);\n            }\n        totalFruits += dp[0][n-1];\n\n        // reset DP; could also just create a second DP\n        for(int i=0; i<n; i++)\n            for(int j=0; j<n; j++)\n                dp[i][j] = 0;\n\n        dp[n-1][n-2] = fruits[n-1][n-2];\n        // kid (n-1, 0) should always stay below both diagonals\n        for(int j=n-3; j>=0; j--)\n            for(int i=max(j+1, n-j-1); i<n; i++) {\n                // check (i, j+1) below both diagonals\n                if(j+1 < i && i+j+1 >= n-1)\n                    dp[i][j] = max(dp[i][j], fruits[i][j] + dp[i][j+1]);\n                // check (i-1, j+1) below both diagonals\n                if(j+1 < i-1 && i+j >=n-1)\n                    dp[i][j] = max(dp[i][j], fruits[i][j] + dp[i-1][j+1]);\n                // check (i+1, j+1) below both diagonals\n                if(j < i && i+j+2>= n-1 && i < n-1)\n                    dp[i][j] = max(dp[i][j], fruits[i][j] + dp[i+1][j+1]);\n            }\n        totalFruits += dp[n-1][0];\n\n        return totalFruits;\n    }\n};\n```
['Dynamic Programming', 'C++']