C++ | Basic DP approach | Tabulation
Intuition\nMy intuition was that the problem can be solved using DP since to calculate cost at each cell we will require the previous moves costs.\n\nIf the mov
# Intuition\nMy intuition was that the problem can be solved using DP since to calculate cost at each cell we will require the previous moves costs.\n\nIf the move can start and end at any cell, I created a 2D dp matrix where each cell represented the maximum cost that can be achieved if it was the destination cell. \n\nTo calculate cost at each cell , there are two possibilities - either its a new move or its the last move of a series of moves. So we take the maximum of them. Since there are two moves - right and bottom, so the costs at each dp cell depends upon its left and top neighbour. \n \n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n\nHere\u2019s how the costs are calculated:\n\n##### For the first row (only right moves): \n- The cost of each cell is calculated as the maximum of two values:\nThe cost to move from j-1 to j, which is grid[i][j]-grid[i][j-1]\nThe maximum cost till grid[i][j-1] plus the cost to move from j-1 to j, which is dp[i][j-1]+grid[i][j]-grid[i][j-1]\n##### For the first column (only down moves): \n- The cost of each cell is calculated as the maximum of two values:\nThe cost to move from i-1 to i, which is grid[i][j]-grid[i-1][j]\nThe maximum cost till grid[i-1][j] plus the cost to move from i-1 to i, which is dp[i-1][j]+grid[i][j]-grid[i-1][j]\n##### For the remaining cells (bottom and right moves): \n- The cost of each cell is calculated as follows:\nIf it is a continued move, the cost is c1 = max(dp[i][j-1]+grid[i][j]-grid[i][j-1], dp[i-1][j]+grid[i][j]-grid[i-1][j])\nIf it is a new move, the cost is c2 = max(grid[i][j]-grid[i][j-1], grid[i][j]-grid[i-1][j])\nThe final cost for the cell is dp[i][j] = max(c1, c2)\n\nFinally, the maximum element in the DP matrix is returned (other than the first element because we need at least one move) \n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: O(m*n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(m*n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int maxScore(vector<vector<int>>& grid) {\n       int m = grid.size(), n = grid[0].size();\n        //create a dp array of size m*n\n        vector<vector<int>> dp(m, vector<int>(n, 0));\n        dp[0][0]=0;\n        int c1,c2;\n        int res=INT_MIN;\n        for(int i=0;i<m;i++){\n            for(int j=0;j<n;j++){\n                if(i==0 && j==0){\n                    continue;\n                }\n                if(i==0){\n                    dp[i][j]=max(grid[i][j]-grid[i][j-1],grid[i][j]-grid[i][j-1]+dp[i][j-1]);\n                    res=max(res,dp[i][j]);\n                }\n                else if(j==0){\n                    dp[i][j]=max(grid[i][j]-grid[i-1][j],grid[i][j]-grid[i-1][j]+dp[i-1][j]);\n                    res=max(res,dp[i][j]);\n                }\n                else{\n                    c1=max(dp[i][j-1]+grid[i][j]-grid[i][j-1],dp[i-1][j]+grid[i][j]-grid[i-1][j]);\n                    c2=max(grid[i][j]-grid[i][j-1],grid[i][j]-grid[i-1][j]);\n                    dp[i][j]=max(c1,c2);  \n                    res=max(res,dp[i][j]); \n                }\n\n\n            }\n          \n        }\n          return res;\n    }\n            \n};\n```
['Dynamic Programming', 'C++']