Snowplough Shortcuts
Medium · dynamic programming
A snowplough works on a grid of m rows and n columns. The number snow[r][c] is the cost of clearing the cell in row r and column c. The plough starts on the top-left cell and must finish on the bottom-right cell. On every move it goes one cell down or one cell right.
The plough pays the clearing cost of every cell it enters, including the first cell and the last cell. It also has k free passes. Using a pass on a cell means that cell costs nothing. A pass can be used on any cell of the route, one pass per cell, and passes you do not use are simply wasted.
Return the smallest total cost of a route from the top-left cell to the bottom-right cell.
Examples
Example 1
Input: snow = [[1, 3, 1], [1, 5, 1], [4, 2, 1]], k = 0
Output: 7
Without passes the cheapest route goes right, right, down, down and pays 1 + 3 + 1 + 1 + 1.
Example 2
Input: snow = [[1, 3, 1], [1, 5, 1], [4, 2, 1]], k = 1
Output: 4
On the same route the pass clears the 3 for free, leaving 1 + 1 + 1 + 1.
Example 3
Input: snow = [[5]], k = 1
Output: 0
The only cell is both the start and the end, and the pass makes it free.
Constraints
- 1 <= m, n <= 30, where m is the number of rows and n the number of columns
- 0 <= snow[r][c] <= 100
- 0 <= k <= 60