Minimum-Electricity Grid Path Moving Only Right or Down
Company: Akuna Capital
Role: Quantitative Researcher
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
Each cell of a rectangular grid holds the amount of electricity, a non-negative integer, that is used when a path passes through that cell. A path starts at the top-left cell and must reach the bottom-right cell, moving one cell right or one cell down at each step. Return the smallest total electricity that any such path uses, counting every cell on the path, including the first and the last.
The candidate's report says only that the task finds the 2D path that uses the least electricity; this version fixes the allowed moves and the cost rule in Rules below.
### Function Signature
```python
def min_power_path(grid: list[list[int]]) -> int:
```
### Rules
- `grid[r][c]` is the electricity used by the cell in row `r` and column `c`; row 0 is the top row and column 0 the leftmost column.
- From cell `(r, c)` a path may move only to `(r, c + 1)` or to `(r + 1, c)`, and it never leaves the grid.
- The cost of a path is the sum of the values of all the cells it visits, including `grid[0][0]` and the bottom-right cell.
- Return the minimum cost over all such paths as a single integer. Only the cost is returned, so it does not matter which of several cheapest paths achieves it.
### Constraints
- `1 <= len(grid) <= 500` and `1 <= len(grid[0]) <= 500`; every row has the same length.
- `0 <= grid[r][c] <= 10^4`
- A path visits at most 999 cells, so every path cost is below `10^7`.
### Examples
**Example 1**
```text
Input: grid = [[2, 7, 1], [3, 1, 4], [5, 2, 1]]
Output: 9
```
The cheapest path moves down, right, down, right and uses `2 + 3 + 1 + 2 + 1 = 9`. Taking the top row first costs `2 + 7 + 1 + 4 + 1 = 15`.
**Example 2**
```text
Input: grid = [[3, 0, 6, 2]]
Output: 11
```
With a single row, the only path crosses every cell: `3 + 0 + 6 + 2 = 11`.
**Example 3**
```text
Input: grid = [[4]]
Output: 4
```
Overview: Find the smallest total electricity used by a path from the top-left to the bottom-right cell of a grid when every step moves right or down and each visited cell adds its cost. Tests reasoning about cheapest paths on a grid, edge cases such as single-row, single-column and one-cell grids, and a solution fast enough for grids of up to 500 by 500 cells.
Each cell of a rectangular grid holds the amount of electricity, a non-negative integer, that is used when a path passes through that cell. A path starts at the top-left cell and must reach the bottom-right cell, moving one cell right or one cell down at each step. Return the smallest total electricity that any such path uses, counting every cell on the path, including the first and the last.
Implement `min_power_path(grid)`.
### Rules
- `grid[r][c]` is the electricity used by the cell in row `r` and column `c`; row 0 is the top row and column 0 the leftmost column.
- From cell `(r, c)` a path may move only to `(r, c + 1)` or to `(r + 1, c)`, and it never leaves the grid.
- The cost of a path is the sum of the values of all the cells it visits, including `grid[0][0]` and the bottom-right cell.
- Return the minimum cost over all such paths as a single integer. Only the cost is returned, so it does not matter which of several cheapest paths achieves it.
### Constraints
- `1 <= len(grid) <= 500` and `1 <= len(grid[0]) <= 500`; every row has the same length.
- `0 <= grid[r][c] <= 10^4`
- A path visits at most 999 cells, so every path cost is below `10^7`. The answer never exceeds 2^31 - 1, so a signed 32-bit integer holds it.
### Examples
**Example 1**
```text
Input: grid = [[2, 7, 1], [3, 1, 4], [5, 2, 1]]
Output: 9
```
The cheapest path moves down, right, down, right and uses `2 + 3 + 1 + 2 + 1 = 9`. Taking the top row first costs `2 + 7 + 1 + 4 + 1 = 15`.
**Example 2**
```text
Input: grid = [[3, 0, 6, 2]]
Output: 11
```
With a single row, the only path crosses every cell: `3 + 0 + 6 + 2 = 11`.
Constraints
- 1 <= len(grid) <= 500 and 1 <= len(grid[0]) <= 500; every row has the same length.
- 0 <= grid[r][c] <= 10^4
- A path visits at most 999 cells, so every path cost is below 10^7 (always within a signed 32-bit integer).
Examples
Input: ([[4]],)
Expected Output: 4
Explanation: Minimum valid grid (source example 3): the single cell is both start and end, so its value is the answer.
Input: ([[10000]],)
Expected Output: 10000
Explanation: Singleton at the value bound 10^4: the lone cell is counted exactly once.
Hints
- Every right/down path visits exactly len(grid) + len(grid[0]) - 1 cells and always includes both corner cells.
- A cell in the top row or in the leftmost column can be reached by exactly one path.
- Taking the cheaper neighbouring cell at every step does not always give the cheapest total.