README.md

2140. 解决智力问题

English Version

题目描述

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

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

• 比方说，给你 questions = [[3, 2], [4, 3], [4, 4], [2, 5]] ：

  <ul>
  	<li>如果问题&nbsp;<code>0</code>&nbsp;被解决了， 那么你可以获得&nbsp;<code>3</code>&nbsp;分，但你不能解决问题&nbsp;<code>1</code> 和&nbsp;<code>2</code>&nbsp;。</li>
  	<li>如果你跳过问题&nbsp;<code>0</code>&nbsp;，且解决问题&nbsp;<code>1</code>&nbsp;，你将获得 <code>4</code> 分但是不能解决问题&nbsp;<code>2</code> 和&nbsp;<code>3</code>&nbsp;。</li>
  </ul>
  </li>
  

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

 

示例 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 分。

 

提示：

• 1 <= questions.length <= 105
• questions[i].length == 2
• 1 <= pointsi, brainpoweri <= 105

解法

方法一：记忆化搜索

Python3

class Solution:
    def mostPoints(self, questions: List[List[int]]) -> int:
        @cache
        def dfs(i):
            if i >= len(questions):
                return 0
            return max(questions[i][0] + dfs(i + questions[i][1] + 1), dfs(i + 1))

        return dfs(0)

Java

class Solution {
    private long[] memo;
    private int[][] questions;

    public long mostPoints(int[][] questions) {
        this.questions = questions;
        memo = new long[questions.length];
        Arrays.fill(memo, -1);
        return dfs(0);
    }

    private long dfs(int i) {
        if (i >= questions.length) {
            return 0;
        }
        if (memo[i] != -1) {
            return memo[i];
        }
        long ans = Math.max(questions[i][0] + dfs(i + questions[i][1] + 1), dfs(i + 1));
        memo[i] = ans;
        return ans;
    }
}

C++

class Solution {
public:
    long long mostPoints(vector<vector<int>>& questions) {
        vector<long long> memo(questions.size(), -1);
        return dfs(0, questions, memo);
    }

    long long dfs(int i, vector<vector<int>>& questions, vector<long long>& memo) {
        if (i >= questions.size()) return 0;
        if (memo[i] != -1) return memo[i];
        long long ans = max(questions[i][0] + dfs(i + questions[i][1] + 1, questions, memo), dfs(i + 1, questions, memo));
        memo[i] = ans;
        return ans;
    }
};

Go

func mostPoints(questions [][]int) int64 {
	n := len(questions)
	memo := make([]int, n)
	for i := range memo {
		memo[i] = -1
	}
	var dfs func(i int) int
	dfs = func(i int) int {
		if i >= n {
			return 0
		}
		if memo[i] != -1 {
			return memo[i]
		}
		ans := max(questions[i][0]+dfs(i+questions[i][1]+1), dfs(i+1))
		memo[i] = ans
		return ans
	}
	return int64(dfs(0))
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

TypeScript

...