Simple | Minimum top-left | DP
Intuition\nDynamic Programming\n\n# Approach\ndp[i][j] will help to save value of minimum value of the top-left rectangle.\n\nMax score of jumping to have the d
# Intuition\nDynamic Programming\n\n# Approach\n`dp[i][j]` will help to save value of minimum value of the top-left rectangle.\n\nMax score of jumping to have the destination at a cell (i, j) is the different between `grid[i][j]` and minimum number in the top-left rectangle (except (i, j) because requirement `you have to make at least one move`). That\'s why I calculated `res = max(res, grid[i][j]-val)` before `dp[i][j] = min(val, grid[i][j])`.\n\nExample:\n`grid = [[9,5,7,3],[8,9,6,1],[6,7,14,3],[2,5,3,1]]`\nMax Score at (2,2) is `14-5` because 5 is the minimum value in the retangle from (0,0) to (2,2).\n\n\n\n# Complexity\n- Time complexity: `O(m*n)`\n- Space complexity: `O(m*n)`\n\n# Code\n```\nfunc maxScore(grid [][]int) int {\n\tm, n := len(grid), len(grid[0])\n\tdp := make([][]int, m)\n\tres := math.MinInt\n\tfor i := range m {\n\t\tdp[i] = make([]int, n)\n\t}\n\tfor i := 0; i < m; i++ {\n\t\tfor j := 0; j < n; j++ {\n\t\t\tval := math.MaxInt\n\t\t\tif In(grid, i-1, j) {\n\t\t\t\tval = min(val, dp[i-1][j])\n\t\t\t}\n\t\t\tif In(grid, i, j-1) {\n\t\t\t\tval = min(val, dp[i][j-1])\n\t\t\t}\n\t\t\tres = max(res, grid[i][j]-val)\n\t\t\tdp[i][j] = min(val, grid[i][j])\n\t\t}\n\t}\n\treturn res\n}\n\nfunc In[T any](mat [][]T, i, j int) bool {\n\treturn i >= 0 && i < len(mat) &&\n\t\tj >= 0 && (len(mat) == 0 || j < len(mat[0]))\n}\n```
['Go']