Minimum Internet Install Cost
MediumDynamic Programming · Adobe
A street has n houses in a row, and every house must get internet from exactly one of k providers. You are given an n x k grid costs, where costs[i][j] is the price of installing provider j at house i.
Two adjacent houses (i and i + 1) may not use the same provider. Houses that are not next to each other may reuse a provider freely.
Return the minimum total installation cost for the whole street. If there are no houses, return 0.
Example 1
- Input:
- costs = [[1, 5, 6], [1, 4, 9], [7, 2, 3]]
- Output:
- 8
- Explanation
- Taking the cheapest provider everywhere would put provider 0 on the first two houses, which is not allowed. The best valid plan is provider 0, then provider 1, then provider 2, costing 1 + 4 + 3 = 8 (provider 1, 0, 1 for 5 + 1 + 2 also ties at 8).
Example 2
- Input:
- costs = [[3, 7], [5, 2], [6, 4]]
- Output:
- 11
- Explanation
- With only two providers the houses must alternate. Starting with provider 0 costs 3 + 2 + 6 = 11; starting with provider 1 costs 7 + 5 + 4 = 16, so the answer is 11.
Example 3
- Input:
- costs = [[9, 4, 6, 8]]
- Output:
- 4
- Explanation
- A single house has no neighbor to conflict with, so it simply takes its cheapest provider, 4.
Constraints
0 <= costs.length <= 10^42 <= costs[i].length <= 20, and every row has the same lengthk0 <= costs[i][j] <= 1000