2140. Solving Questions With Brainpower - Medium

前往題目

想法

• 選或不選都要考慮

思路

題目解釋得很糟糕，這題的目的就是當前問題解決了就要跳過接下來的brainpower個問題，不解決就下一個

1. 用遞迴的方式
2. 每次都紀錄選與不選的結果
3. 紀錄每個題目的最大可能值，這樣後面遇到就不需要再重算

Code

class Solution {
    // Record the questions already been considered
    // question -> points
    Map<Integer, Long> map;

    public long mostPoints(int[][] questions) {
        map = new HashMap();
        long res = dfs(0, questions);
        return res;
    }

    private long dfs(int i, int[][] questions) {
        // Out of bound already
        if (i >= questions.length) return 0;
        if (map.containsKey(i)) return map.get(i);

        // Skip this question
        long notSelect = dfs(i + 1, questions);

        // Select this question
        // Obtain points of the current question
        // Jump to the solvable question
        long select = questions[i][0] + dfs(i + 1 + questions[i][1], questions);
        
        // Memorize
        map.put(i, Math.max(notSelect, select));

        return Math.max(notSelect, select);
    }
}