魔理沙的魔导书挑战

题目描述

魔理沙初始拥有 E 点魔力值，她面前依次排列着 n 本被魔法结界保护的魔导书。对于第 i 本魔导书，魔理沙可以选择挑战结界或直接跳过：

1. 挑战结界：只有当魔理沙当前的魔力值严格大于该结界消耗值 a[i] 时，才能挑战成功。挑战成功后，魔力值变为 current − a[i] + b[i]。
2. 跳过：魔理沙不挑战该结界，直接前往下一本书，魔力值保持不变。

魔理沙希望在保证挑战过程中魔力值始终不为负数的情况下，尽可能多地收纳魔导书。请计算她最多能成功挑战多少个结界。

数据范围：

• 1 ≤ E ≤ 10⁹
• 1 ≤ a[i], b[i] ≤ 10⁹
• 1 ≤ n ≤ 100

示例

输入：

18
15 17 4 18
1 15 4 17

输出： 2

说明：

• 初始魔力 18
• 跳过第 1 本书（消耗 15，反馈 1），魔力仍为 18
• 挑战第 2 本书：18 > 17，成功。魔力变为 18 − 17 + 15 = 16
• 挑战第 3 本书：16 > 4，成功。魔力变为 16 − 4 + 4 = 16
• 第 4 本书消耗 18，当前魔力 16 ≤ 18，只能跳过
• 最终挑战数量 = 2

解题思路

为什么不能用魔力值作为 DP 维度？ 魔力值范围高达 10⁹，直接以魔力值为维度会内存溢出。

正确做法：以挑战本数为维度

定义 dp[j]：挑战 j 本书后能达到的最大魔力值，-1 表示不可能。

状态转移（按书顺序处理，每本书可以选择挑战或跳过）：

• 跳过：dp[j] 不变
• 挑战：若 dp[j] > a[i]（严格大于才可挑战），则 dp[j+1] = max(dp[j+1], dp[j] - a[i] + b[i])

关键点： 逆序遍历 j，保证每本书最多挑战一次（类似背包）。

代码实现

function maxGrimoires(E, costs, gains) {
    const n = costs.length;

    // dp[j] = 挑战 j 本书后能达到的最大魔力值，-1 表示不可能
    const dp = new Array(n + 1).fill(-1);
    dp[0] = E;

    for (let i = 0; i < n; i++) {
        const cost = costs[i];
        const gain = gains[i];
        // 逆序遍历：每本书最多挑战一次
        for (let j = i; j >= 0; j--) {
            if (dp[j] > cost) {                                        // 严格大于才能挑战
                dp[j + 1] = Math.max(dp[j + 1], dp[j] - cost + gain); // 挑战：取最大魔力值
            }
        }
    }

    // 找到最大的 j 使得 dp[j] ≠ -1
    for (let j = n; j >= 0; j--) {
        if (dp[j] !== -1) return j;
    }
    return 0;
}

复杂度分析

• 时间复杂度： O(n²)，n ≤ 100，外层遍历书籍，内层逆序遍历挑战数量。
• 空间复杂度： O(n)，一维 dp 数组。

18
15 17 4 18
1 15 4 17

2