解决智力问题 | 前端芯事

题目

自己想的超时～

从前往后解决智力题时，我们会得到一个冷却时间，冷却时间内我们不能做后面的题，所以我记录了做每道题时的冷却时间和对应得到的分数。

function mostPoints(questions: number[][]): number {
    let dp = []
    let max = 0;

    for (let [v, cd] of questions) {
        const lastDp = dp;

        const dict = {
            [cd]: v,
        }
        for (let [val, cd2] of lastDp) {
            if (cd2 >= 1) {
                dict[cd2-1] = Math.max(dict[cd2-1] ?? 0, val);
            } else {
                dict[cd] = Math.max(dict[cd], val + v);
            }
        }

        for (let [cd, v] of Object.entries(dict)) {
            dp.push([v, cd]);
            max = Math.max(max, v)
        }
    }

    return max;
};

不出意外，提交后超时了，原因在于每一次答题时，都需要额外的处理冷却时间的减少，而且有大量冗余的数据。

正确做法

做了第 x 题后，那么它后面的一定冷却时间内的题都不能做。

容易想到(真的不容易～)：

如果选择做当前题，那么后面几题都不能做
最后一题，后面没有题，反而是最简单的情况
可以一道题都不做，那么我们的得分将是 0

所以我们不妨把 dp 数组都初始化为 0。总共有 len 题，我们不妨多设置一个位置，表示一道题也不答 dp[len] = 0。

对于最后一个位置，答题不会对后续产生影响，要得分的当然是选择答题，这里隐含了取答题与不答题的最大值的逻辑。

把条件放宽到每一个位置，也是类似的逻辑，我看可以选择不答题，那么我们最大的得分是和下一个位置一致的，如果我们选择答题，那么我们在 i + cd 题后才能继续答题得分。

所以递推关系是：dp[i] = Math.max(dp[i+1], question[i][0] + dp[i+1+question[i][1]])。

下面给出代码实现：

function mostPoints(questions: number[][]): number {
    const len = questions.length;

    const dp = new Array(len+1).fill(0); // 一道题都不做的分数是 0

    for (let i=len-1; i>=0; i--) {
        dp[i] = Math.max(
            dp[i+1], // 不做这道题
            questions[i][0] + (dp[i+1+questions[i][1]] ?? 0), // 做了这道题，接下来的一些题会不能做
        )
    }
    // console.log(dp)
    return Math.max(...dp);
};

题目 ​

自己想的超时～ ​

正确做法 ​

题目

自己想的超时～

正确做法