> For the complete documentation index, see [llms.txt](https://timmybeeflin.gitbook.io/cracking-leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://timmybeeflin.gitbook.io/cracking-leetcode/weekly-contest/weekly-contest-276/2140.-solving-questions-with-brainpower.md).

# 2140. Solving Questions With Brainpower

### my post

<https://leetcode.com/problems/solving-questions-with-brainpower/discuss/1693386/Java-DFS-%2B-memo-and-DP-Solutions-or-T%3A-O(n)-S%3A-O(n)>

## DFS + memo

#### solution 1

use start end  as key

```java
class Solution {
    public long mostPoints(int[][] questions) {
        Map<String, Long> map = new HashMap<>();
        return helper(questions, 0, questions.length - 1, map);
    }
    
    private long helper(int[][] questions, int start, Map<String, Long> map) {
        if (start > end) {
            return 0;
        }
        String key = start + "," + end; // use start, end as key
        if (map.containsKey(key)) {
            return map.get(key);
        }
        
        long cur = questions[start][0] + helper(questions, start + questions[start][1] + 1, end, map);
        long next = helper(questions, start + 1, end, map);
        long res = Math.max(cur, next);
        
        map.put(key, res);
        return map.get(key);
    }
}
```

其實只要對 start 紀錄就好, 因為固定 start 算出的結果是一樣的,  只是之後重複跑時,  會用到, 所以可以做 memo

ex : \[1,2,3,4]

fix index 1, 如果是 skip 1 index(skip index 2), 所以 3 會計算過

之後 fix index 2, 假設不跳過任何 index, 要算 3  時, memo 就有了值了, 可以利用

#### solution 2

所以這裡用 start 為 key, 所以用一個 long array 就可以

```java
class Solution {
    public long mostPoints(int[][] questions) {
        Long[] memo = new Long[questions.length];
        return dfs(questions, 0, memo);
    }
    private long dfs(int[][] questions, int start, Long[] memo) {
        if (start >= memo.length) {
            return 0;
        }
        if (memo[start] != null) {
            return memo[start];
        }
        
        long cur = questions[start][0] + dfs(questions, start + questions[start][1] + 1, memo);
        long next = dfs(questions, start+1, memo);
        
        memo[start] = Math.max(cur, next); // just use start as key, ya it works.
        return memo[start];
    }
}
```

## DP

從上面的 dfs 可以得到靈感

```
dp[i] = Math.max(
    questions[start][0] + dp[start + questions[start][1] + 1], 
    dp[i+1]
);

因為用到 dp[i+1], 所以從後面 for loop
```

這個很 tricky, 開了一個超大的 dp array, 這樣就不用處理越界問題

```java
class Solution {
    public long mostPoints(int[][] questions) {
        int n = questions.length;
        long[] dp = new long[200001];
        
        for (int i = n - 1; i >= 0; i--) {
            dp[i] = Math.max(
                questions[i][0] + dp[i + questions[i][1] + 1], 
                dp[i+1]
            );
        }
        return dp[0];
    }
}
```

處理邊界

T: O(n)

S: O(n)

```java
class Solution {
    public long mostPoints(int[][] questions) {
        int n = questions.length;
        long[] dp = new long[n+1];
        
        for (int i = n - 1; i >= 0; i--) {
            int curIdx = i + questions[i][1] + 1;
            long curValue = (curIdx >= n) ? 0 : dp[curIdx];
            
            dp[i] = Math.max(questions[i][0] + curValue, dp[i+1]);
        }
        return dp[0];
    }
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/weekly-contest/weekly-contest-276/2140.-solving-questions-with-brainpower.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.