leetcode-2140:解决智力问题

简介: leetcode-2140:解决智力问题

题目

题目链接

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

这个数组表示一场考试里的一系列题目,你需要 按顺序 (也就是从问题 0 开始依次解决),针对每个问题选择 解决 或者 跳过 操作。解决问题 i 将让你 获得 pointsi 的分数,但是你将 无法 解决接下来的 brainpoweri 个问题(即只能跳过接下来的 brainpoweri 个问题)。如果你跳过问题 i ,你可以对下一个问题决定使用哪种操作。

比方说,给你 questions = [[3, 2], [4, 3], [4, 4], [2, 5]] :

  • 如果问题 0 被解决了, 那么你可以获得 3 分,但你不能解决问题 1 和 2 。
  • 如果你跳过问题 0 ,且解决问题 1 ,你将获得 4 分但是不能解决问题 2 和 3 。

请你返回这场考试里你能获得的 最高 分数。

示例 1:

输入:questions = [[3,2],[4,3],[4,4],[2,5]]
输出:5
解释:解决问题 0 和 3 得到最高分。
- 解决问题 0 :获得 3 分,但接下来 2 个问题都不能解决。
- 不能解决问题 1 和 2
- 解决问题 3 :获得 2 分
总得分为:3 + 2 = 5 。没有别的办法获得 5 分或者多于 5 分。

示例 2:

输入:questions = [[1,1],[2,2],[3,3],[4,4],[5,5]]
输出:7
解释:解决问题 1 和 4 得到最高分。
- 跳过问题 0
- 解决问题 1 :获得 2 分,但接下来 2 个问题都不能解决。
- 不能解决问题 2 和 3
- 解决问题 4 :获得 5 分
总得分为:2 + 5 = 7 。没有别的办法获得 7 分或者多于 7 分。

解题

方法一:动态规划(倒序DP)

参考链接

class Solution {
public:
    long long mostPoints(vector<vector<int>>& questions) {
        int n=questions.size();
        vector<long long> dp(n+1);
        for(int i=n-1;i>=0;i--){
            vector<int>& q=questions[i];
            int j=i+q[1]+1;
            dp[i]=max(dp[i+1],q[0]+(j<n?dp[j]:0));
        }
        return dp[0];
    }
};
相关文章
|
1月前
|
算法
算法人生(3):从“贪心算法”看“战胜拖延”(完美主义版)
本文探讨了拖延症的一个常见原因——完美主义,并从贪心算法的角度提供启示。贪心算法通过局部最优决策逼近全局最优解,不保证全局最优,但寻求满意解。完美主义者的拖延源于高标准、过度关注细节、压力和时间管理困难。为解决这个问题,建议接受不完美,设定合理目标,追求良好效果,以及培养时间管理技巧。通过实例说明,调整心态和策略,可以提高工作效率并克服拖延。
|
1月前
|
存储
每日一题——leetcode682.棒球比赛
每日一题——leetcode682.棒球比赛
|
1月前
|
机器人
[leetcode 脑子急转弯] 2731. 移动机器人
[leetcode 脑子急转弯] 2731. 移动机器人
|
1月前
|
安全 Java 索引
如何克服Leetcode做题的困境
如何克服Leetcode做题的困境
30 0
|
机器人
LeetCode 双周赛 106(2023/06/10)两道思维题
往期回顾:[LeetCode 单周赛第 348 场 · 数位 DP 模版学会了吗?](https://mp.weixin.qq.com/s/4aLHpyaLOUEHSaX2X8e5FQ)
67 0
LeetCode 双周赛 106(2023/06/10)两道思维题
|
算法
敢不敢挑战这道《简单题》
这道题的题目和代码都很长,但是细节满满,值得一写
45 0
|
C++
【力扣·每日一题】913. 猫和老鼠(C++ 记忆化搜索 博弈)
【力扣·每日一题】913. 猫和老鼠(C++ 记忆化搜索 博弈)
173 0
【力扣·每日一题】913. 猫和老鼠(C++ 记忆化搜索 博弈)
086.爱因斯坦的数学题
086.爱因斯坦的数学题
77 0
088.马克思手稿中的数学题
088.马克思手稿中的数学题
74 0
|
机器学习/深度学习 人工智能
把所有的谎言献给你β(找规律数学题)
梓川咲太的面前坐着野兔先辈,作为约定,只好乖乖的打开笔记本开始学习了。 “加法符号写歪了,变成了乘法符号,在算式的第三行那个地方。”樱岛麻衣突然开口。
116 0
把所有的谎言献给你β(找规律数学题)

热门文章

最新文章