Maximum Grid Path Score Within a Budget
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
You are given an `m` by `n` integer grid and an integer budget `k`. Start at the top-left cell `(0,0)` and reach the bottom-right cell `(m-1,n-1)`, moving only right or down.
Each visited cell contributes both score and cost:
| Cell value | Added score | Added cost |
|---|---:|---:|
|0|0|0|
|1|1|1|
|2|2|1|
Return the greatest total score of a path whose total cost is at most `k`. Return `-1` if no such path exists. The destination cell contributes its score and cost too; merely reaching it does not excuse an over-budget path. The starting cell is guaranteed to contain zero.
```cpp
class Solution {
public:
int maxPathScore(vector<vector<int>>& grid, int k);
};
```
### Examples
**Example 1:**
```text
Input: grid = [[0,2,1],[1,0,2]], k = 2
Output: 4
Explanation: Right, down, right visits values 0,2,0,2 for score 4 and cost 2. The path with score 5 costs 3 and is invalid; the other path scores 3 at cost 2.
```
**Example 2:**
```text
Input: grid = [[0,0],[0,2]], k = 0
Output: -1
Explanation: Every route must visit the destination value 2, which incurs cost 1. No route fits the zero budget.
```
### Constraints
- `1 <= m, n <= 200`.
- `0 <= k <= 1000`.
- `grid[0][0] == 0`.
- `0 <= grid[i][j] <= 2`.
### Clarifying Questions
- Are diagonal or backward moves allowed? No.
- Does a value of 2 cost two? No; its score is two and its cost is one.
- Is cost exactly `k` required? No; any total cost at most `k` is allowed.
- What happens for a one-cell grid? Its guaranteed zero-valued cell is already the destination, giving score zero at cost zero.
### What a Strong Answer Covers
- Legal paths and the separate score and cost rules for every visited cell.
- The budget condition at the destination and correct impossibility behavior.
- Zero budgets, zero-valued cells, narrow grids, and the single-cell case.
- An optimality proof and time and memory bounds for all dimensions and budgets.
### Follow-up Questions
- What extra output would be needed to return an actual maximizing path?
- How would requiring cost exactly `k` change the acceptance condition?
```hint Keep score and cost as separate state information
For each cell and exact spent cost, retain the greatest reachable score. Arrivals come from above or the left, and the current cell adds its own score and cost. Unreachable states must remain distinct from reachable score zero. The previous-row and current-row states can share a rolling storage layout.
```
Overview: Maximize a right-or-down grid path score within a cost budget. Covers destination costs, impossible paths, examples, proof, and a C++ solution.