Swift | Dynamic Programming
The main idea is that the score depends only on the starting and ending cells and not on the specific path.\n\nThis observation allows us to compute the max sco
The main idea is that the score depends only on the starting and ending cells and not on the specific path.\n\nThis observation allows us to compute the max score in linear time using dynamic programming.\n\n# Code\n```\nclass Solution {\n    func maxScore(_ grid: [[Int]]) -> Int {\n        let (m, n) = (grid.count, grid.first?.count ?? 0)\n\n        // For each cell, compute the min value to its left, above or in the first\n        // quadrant.\n        var mins = Array(repeating: Array(repeating: 0, count: n), count: m)\n        for row in 0..<m {\n            for col in 0..<n {\n                var minValue = Int.max\n                if row > 0 { minValue = min(minValue, grid[row - 1][col], mins[row - 1][col]) }\n                if col > 0 { minValue = min(minValue, grid[row][col - 1], mins[row][col - 1]) }\n\n                mins[row][col] = minValue\n            }\n        }\n\n        // For each cell, compute the score from the min value to the cell.\n        var res = Int.min\n        for row in 0..<m {\n            for col in 0..<n {\n                res = max(res, grid[row][col] - mins[row][col])\n            }\n        }\n        return res\n    }\n}\n```
['Swift']