[LeetCode] 2140. Solving Questions With Brainpower

Problem: https://leetcode.com/problems/solving-questions-with-brainpower/description/

Similar to the House Robber problem. For each question, we need to consider these 2 cases:

The point we can get if we solve this problem and solve or skip the next eligible problem.

The point we can get if we skip this problem and solve or skip the next eligible problem.

Time Complexity : O ( N )

Space Complexity : O ( N )

class Solution {
    public long mostPoints(int[][] questions) {
        int N = questions.length;

        // maximum point when pick the 'i' question
        long[] pick = new long[N];
        // maximum point when skip the 'i' question
        long[] skip = new long[N];

        for (int i = N-1; i >= 0; i--) {
          // solve the 'i' question
          pick[i] = questions[i][0];

          int j = i + questions[i][1] + 1;
          if (j < N) {
            // add on the point of picking / skip next eligible question 
            pick[i] += Math.max(pick[j], skip[j]);
          }

          // skip the 'i' question
          if (i + 1 < N) {
            // add on the point of picking / skip the next question 
            skip[i] = Math.max(pick[i+1], skip[i+1]);
          }
        }

        return Math.max(pick[0], skip[0]);
    }
}