LeetCode5982 解决智力问题

发表于 | 分类于 |
字数统计: 807 | 阅读时长 ≈ 3

链接: https://leetcode-cn.com/problems/solving-questions-with-brainpower/

题意

给你一个下标从 0 开始的二维整数数组 questions ，其中$questions[i] = [pointsi, brainpoweri]$

这个数组表示一场考试里的一系列题目，你需要 按顺序 ，针对每个问题选择解决或者跳过操作。解决问题 i 将让你获 pointsi 的分数，但是你只能跳过接下来的 brainpoweri 个问题。如果你跳过问题 i ，你可以对下一个问题决定使用哪种操作。
求这场考试里你能获得的 最高 分数。

解法

一眼dp
但是周赛的时候写了一个小时也没完全写对
果然我需要解决一下智力问题
我是废物.jpg
一开始考虑dp[i]表示解决到第i个问题可以获得的最大分数
但是发现状态转移的时候 我没法知道前一个最大分数的位置在哪里
所以就时间复杂度O(n^2)卡住了
记忆化搜索也没有写出来 直接dfs超时
场面陷入困境
正解是倒序dp，令dp[i]表示从第i个问题到最后一个问题可以获得的最大分数
如果不做当前题目dp[i + 1]
做的话questions[i][0] + dp[i + questions[i][1] + 1]
取两者的较大值即可

但其实也可以正序dp做
只是在每次做第i个问题的时候 更新的是下一个不被跳过的问题的dp值
对于超出索引的情况，我们可以将其更新到一个特殊的值 dp[n]中
表示当前问题做了且为最后一个问题

代码

记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    long long ans;
    unordered_map<int, long long> visit;
    long long dfs(int loc, vector<vector<int>>& questions)
    {
        if (loc >= questions.size()) {
            return 0;
        }
        if (visit[loc]) return visit[loc]; 
        long long sel = questions[loc][0], unsel = 0;
        // 做
        sel += dfs(loc + questions[loc][1] + 1, questions);
        // 不做
        unsel = dfs(loc + 1, questions);
        visit[loc] = max(sel, unsel); // 记忆化搜索
        return visit[loc]; 
        
    }
    long long mostPoints(vector<vector<int>>& questions) {
        long long ans = 0;
        int n = questions.size();
        for (int i = 0; i < n; i++) {
            // 如果这个位置已经计算过
            if (visit[i] != 0) {
                ans = max(ans, visit[i]);
            }
            else {
                ans = max(ans, dfs(i, questions));
            }
        }
        return ans;
//         [[21,5],[92,3],[74,2],[39,4],[58,2],[5,5],[49,4],[65,3]]
//         157       
    }
};

倒序dp（最推荐）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
long long mostPoints(vector<vector<int>>& questions) {
    int n = (int)questions.size();
    vector<long long> dp(n + 1);
    // dp[i]表示第i个问题到最后一个问题的最大值(0-indexed)
    for (int i = n - 1; i >= 0; i--) {
        if (i + questions[i][1] + 1 < n) {
            dp[i] = max(dp[i + 1], questions[i][0] + dp[i + questions[i][1] + 1]);
        }
        else {
            dp[i] = max(dp[i + 1], (long long)questions[i][0]);
        }
    }
    
    return dp[0];
}

正序dp

1
2
3
4
5
6
7
8
9
10
11
long long mostPoints(vector<vector<int>>& questions) {
    int n = (int)questions.size();
    vector<long long> dp(n + 1);
    // dp[i][0]表示第i个问题做或者不做的最大分数(1-indexed)
    for (int i = 0; i < n; i++) {
        dp[i + 1] = max(dp[i], dp[i + 1]);
        int nxt = min(n, i + 1 + questions[i][1]); // 如果超过索引都保存到dp[n]中
        dp[nxt] = max(dp[nxt], dp[i] + questions[i][0]);
    }
    return dp[n];
}