Easy Solution using DP C++
Intuition\n The problem involves traversing a grid to find the maximum score attainable by following certain rules. Initially, we might consider a brute-force a
# Intuition\n The problem involves traversing a grid to find the maximum score attainable by following certain rules. Initially, we might consider a brute-force approach of exploring all possible paths from the starting point to the ending point, but this would be inefficient. Instead, we can leverage dynamic programming to efficiently compute the maximum score.\n\n# Approach\nWe approach this problem using dynamic programming. We create a 2D DP array to store the maximum score attainable from each cell. We start from the bottom-right corner of the grid and work our way towards the top-left corner. For each cell, we compute the maximum score by considering the scores from the adjacent cells and the current cell\'s score. We update the DP array accordingly. Once we have filled the DP array, we traverse the grid again to find the maximum score while considering the constraints of not visiting cells that have been visited in the previous traversal.\n\n# Complexity\n- Time complexity:\n The time complexity of our approach is O(n * m), where n is the number of rows and m is the number of columns in the grid. This is because we traverse the grid twice: once to fill the DP array and once to find the maximum score. In each traversal, we visit each cell once, leading to a total time complexity of O(n * m).\n\n- Space complexity:\n The space complexity of our approach is also O(n * m). This is because we use a 2D DP array to store intermediate results. The size of this array is proportional to the size of the input grid, which is n * m. Therefore, the space complexity is O(n * m).\n\n\n# Code\n```\nclass Solution {\npublic:\n    int maxScore(vector<vector<int>>& grid) {\n       int rows = grid.size();\nint cols = grid[0].size();\n\nstd::vector<std::vector<int>> dp(rows, std::vector<int>(cols, std::numeric_limits<int>::min()));\ndp[rows - 1][cols - 1] = grid[rows - 1][cols - 1];\n\nfor (int i = rows - 1; i >= 0; --i) {\nfor (int j = cols - 1; j >= 0; --j){\nif (i < rows - 1)\ndp[i][j] = std::max(dp[i][j], dp[i + 1][j]);\nif (j < cols - 1)\ndp[i][j] = std::max(dp[i][j], dp[i][j + 1]);\ndp[i][j] = std::max(dp[i][j], grid[i][j]);\n}\n}\n\nint maxscore = std::numeric_limits<int>::min();\nfor (int i = 0; i < rows; ++i) {\nfor (int j = 0; j < cols; ++j) {\nif (i < rows - 1)\nmaxscore = std::max(maxscore, dp[i + 1][j] - grid[i][j]);\nif (j < cols - 1)\nmaxscore = std::max(maxscore, dp[i][j + 1] - grid[i][j]);\n}\n}\nreturn maxscore;\n    }\n};\n\n\n```
['C++']