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

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 就可以

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, 這樣就不用處理越界問題

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)

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];
    }
}