🔥Clean Code💯 with Best Explanation🔥||⚡BottomUP DP🌟
Here if u will observe carefully then u will find that for each starting cell there is no need to take choice for all the below rows as well as right columns be
### Here if u will observe carefully then u will find that for each starting cell there is no need to take choice for all the below rows as well as right columns because the best score for a particular starting cell will always be equal to the maximum difference between the final ending cell & the starting cell as because all the intermediate cells will be cancelled out(as we know that starting cell value is fixed so to bring max difference we have to find the final cell having the max value). \n## ***The Search Space for final ending cell is as follows:-***\n`Suppose if the coordinates of the starting cell is (i, j) then the final cell coordinates (x, y) range will be x >=i && x < m whereas y >= j && y < n`\n\n## *Prove of how intermediates cells values are cancelled out:-*\n## Suppose value of any particular starting cell is c1 & that of final ending cell be c5 then the intermediates cells values will be c2, c3, c4 & so the score for that particular path will be `(c2 - c1) + (c3 - c2) + (c4 - c3) + (c5 - c4)` = c5 - c1 (all others cancel each other\uD83D\uDE01). Hence Proved.\n\n# Now observe my code carefully u will get it 100%.\n## `For any query u can comment below, I will surely ans it\uD83E\uDD17`\n\n## Connect with me on LinkedIN : https://www.linkedin.com/in/aditya-jhunjhunwala-51b586195/\n\n# Complexity\n```\n- Time complexity:\nO(m * n)\n\n- Space complexity:\nO(1)\n```\n\n# Code\n## Please Upvote if it helps\uD83E\uDD17\n```\nclass Solution {\npublic:\n    int maxScore(vector<vector<int>>& grid) {\n        int m = grid.size(), n = grid[0].size(), ans = INT_MIN;\n        for(int i = m - 1 ; i >= 0 ; i--){\n            for(int j = n - 1 ; j >= 0 ; j--){\n                if(i == m - 1 && j == n - 1)\n                    continue;\n                int maxi = INT_MIN;\n                if(i != m - 1)\n                    maxi = max(maxi, grid[i + 1][j]);\n                if(j != n - 1)\n                    maxi = max(maxi, grid[i][j + 1]);\n                ans = max(ans, maxi - grid[i][j]);\n                grid[i][j] = max(maxi, grid[i][j]);\n            }\n        }\n        return ans;\n    }\n};\n```
['Dynamic Programming', 'Greedy', 'C++']