37. Minimum Plans to Reach Target Bandwidth

Origin: HackerRank Prep Kit #37

题目描述

给定一个数组 planSizes 和一个整数 targetBandwidth，返回恰好凑齐 targetBandwidth 所需的最少 plan 数量。如果不可能，返回 -1。每个 plan 可以无限次使用。

示例

Example 1

Input: planSizes = [1, 2, 5], targetBandwidth = 11 Output: 3 Explanation: 5 + 5 + 1 = 11，用了 3 个 plan。

Example 2

Input: planSizes = [1, 3, 4, 7], targetBandwidth = 10 Output: 2 Explanation: 7 + 3 = 10，用了 2 个 plan。

Sample Input 0

1 5 5

Output: 1（一个 5 Mbps 的 plan 恰好等于 target 5）

Sample Input 1

3 1 2 5 11

Output: 3

约束

• 1 <= planSizes.length <= 1000
• 1 <= planSizes[i] <= 10000
• 0 <= targetBandwidth <= 100000

关键信息

• 每个 plan 可无限次使用 → 完全背包问题
• 求最少 plan 数量 → 最少硬币数（LeetCode 322 Coin Change）
• target = 0 时返回 0

Resolution

我的解法

function findMinimumPlansForBandwidth(planSizes: number[], targetBandwidth: number): number {
    let dp: number[] = Array.from({ length: targetBandwidth + 1 }, () => Infinity)
    dp[0] = 0
    for (let i = 1; i <= targetBandwidth; i++) {
        for (let j = 0; j < planSizes.length; j++) {
            let planSize = planSizes[j]
            if (dp[i - planSize] !== undefined) {
                dp[i] = Math.min(dp[i], dp[i - planSize] + 1)
            }
        }
    }
    return dp[targetBandwidth] === Infinity ? -1 : dp[targetBandwidth]
}

解题思路

完全背包 / 硬币找零（LeetCode 322 Coin Change）。每个 plan 可无限次使用，求凑齐 target 的最少 plan 数。

• dp[i] = 凑齐带宽 i 所需的最少 plan 数
• dp[0] = 0，其他初始化为 Infinity（代表无解）
• 对每个 i，遍历所有 planSize，dp[i] = min(dp[i], dp[i - planSize] + 1)
• 最后 dp[target] 是 Infinity 返回 -1，否则返回 dp[target]

踩坑：贪心不行

反例：planSizes = [1, 3, 4], target = 6

• 贪心：4 + 1 + 1 = 3 个
• 最优：3 + 3 = 2 个

贪心在这类”完全背包求最少数量”问题上没有最优子结构。

复杂度

• 时间：O(n × target)，n 是 planSizes 长度
• 空间：O(target)