✅✅Beats 100% Users ✅ Easy Solution ✅ Best Approaches✅
Intuition\nThe problem involves finding the maximum score possible while moving from the top-left corner to the bottom-right corner of the grid. You can move ei
# Intuition\nThe problem involves finding the maximum score possible while moving from the top-left corner to the bottom-right corner of the grid. You can move either right or down at each step. The score of the path is determined by the difference between the values of the cells along the path. \n\n# Approach\n1. **Dynamic Programming**: The solution uses dynamic programming to efficiently compute the maximum score for each cell in the grid.\n2. **Backward Propagation**: The algorithm starts from the bottom-right corner and iteratively computes the maximum score for each cell by propagating backward.\n\nThe approach involves the following steps:\n- Initialize a 2D DP array to store intermediate results. Initialize each cell with a value of `INT_MIN`.\n- Propagate backward from the bottom-right corner to the top-left corner of the grid.\n- For each cell, calculate the maximum score by considering both the rightward and downward paths.\n- Store the maximum score for each cell in the DP array.\n- After completing the DP array, iterate through it to find the maximum score.\n\n## Complexity\n- **Time complexity**: $$O(n \\cdot m)$$, where \\( n \\) is the number of rows and \\( m \\) is the number of columns in the grid. This complexity arises from iterating through each cell of the grid once and performing some operations in each cell.\n- **Space complexity**: $$O(n \\cdot m)$$, as the algorithm uses a 2D DP array of size \\( n \\times m \\) to store intermediate results.\n\nThis approach efficiently computes the maximum score for the given grid.\n# Code\n```\n#include <vector>\n#include <algorithm>\n#include <climits>\n\nusing namespace std;\n\nclass Solution\n{\n    int solveop(vector<vector<int>> &grid, vector<vector<int>> &dp, int i, int j)\n    {\n        int n = grid.size();\n        int m = grid[0].size();\n\n        for (int o = j + 1; o < m; o++)\n        {\n            int k = grid[i][o] - grid[i][j];\n            dp[i][j] = max(dp[i][j], max(k + dp[i][o], k));\n        }\n        for (int o = i + 1; o < n; o++)\n        {\n            int k = grid[o][j] - grid[i][j];\n            dp[i][j] = max(dp[i][j], max(k + dp[o][j], k));\n        }\n        return dp[i][j]; // Added return statement\n    }\n    \n    int solvedp(vector<vector<int>> &grid, vector<vector<int>> &dp)\n    {\n        int n = grid.size();\n        int m = grid[0].size();\n\n        for (int i = m - 2; i >= 0; i--)\n        {\n            for (int j = i + 1; j < m; j++)\n            {\n                if (j != m - 1)\n                {\n                    int k = grid[n - 1][j] - grid[n - 1][i];\n                    dp[n - 1][i] = max(dp[n - 1][i], max(k + dp[n - 1][j], k));\n                }\n                else\n                {\n                    int k = grid[n - 1][j] - grid[n - 1][i];\n                    dp[n - 1][i] = max(dp[n - 1][i], k);\n                }\n            }\n        }\n\n        for (int i = n - 2; i >= 0; i--)\n        {\n            for (int j = i + 1; j < n; j++)\n            {\n                if (j != n - 1)\n                {\n                    int k = grid[j][m - 1] - grid[i][m - 1];\n                    dp[i][m - 1] = max(dp[i][m - 1], max(k + dp[j][m - 1], k));\n                }\n                else\n                {\n                    int k = grid[j][m - 1] - grid[i][m - 1];\n                    dp[i][m - 1] = max(dp[i][m - 1], k);\n                }\n            }\n        }\n\n        for (int i = n - 2; i >= 0; i--)\n        {\n            for (int j = m - 2; j >= 0; j--)\n            {\n                solveop(grid, dp, i, j);\n            }\n        }\n        int ans = INT_MIN;\n        for (int i = n - 2; i >= 0; i--)\n        {\n            ans = max(ans, dp[i][m - 1]);\n        }\n        for (int i = m - 2; i >= 0; i--)\n        {\n            ans = max(ans, dp[n - 1][i]);\n        }\n        for (int i = n - 2; i >= 0; i--)\n        {\n            for (int j = m - 2; j >= 0; j--)\n            {\n                ans = max(ans, dp[i][j]);\n            }\n        }\n        return ans;\n    }\n\npublic:\n    int maxScore(vector<vector<int>> &grid)\n    {\n        int n = grid.size();\n        int m = grid[0].size();\n        vector<vector<int>> dp(n, vector<int>(m, INT_MIN));\n        return solvedp(grid, dp);\n    }\n};\n\n```
['C++']