A courier crosses a city grid toll from the top-left block to the bottom-right block, moving only right or down. Entering block (i, j) costs toll[i][j] (the start block is paid too). Return the smallest total toll.
Examples
Input: toll = [[3, 1, 4],
[1, 5, 9],
[2, 6, 5]]
Output: 17
Explanation: 3 -> 1 -> 2 -> 6 -> 5 going down, down, right, right.
Input: toll = [[7]]
Output: 7
Constraints
1 <= rows, cols <= 1000 <= toll[i][j] <= 1000- Target complexity: O(rows * cols).
Goals
- Express the cheapest way into a cell through its two possible predecessors
- Handle the first row and first column as special cases