Classic Dynamic Programming

Hints that a problem requires Dynamic Programming:

1/ Starts with the problem asking for a Max or Min

2/ It usually consists of a search problem

3/ The search, for each "node", always has a dual condition: include the "node" in your search and pay a cost X, or don't include it and pay a cost Y

4/ A brute-force solution will be intractable. For example, you may end up with a complexity of 2^N, where N = 10^5...

5/ Sometimes the solution is so large that the description of the problem asks you to module the result by 10^9+7...

This one is a classic one. Create an array of solutions called DP. Start with the last question, which only has one solution (itself). Work backwards and at each "node", take the max between not including it and including it. Linear space, linear time. Code is down below, cheers, ACC.

Solving Questions With Brainpower - LeetCode

2140. Solving Questions With Brainpower

Medium

You are given a 0-indexed 2D integer array questions where questions[i] = [pointsi, brainpoweri].

The array describes the questions of an exam, where you have to process the questions in order (i.e., starting from question 0) and make a decision whether to solve or skip each question. Solving question i will earn you pointsi points but you will be unable to solve each of the next brainpoweri questions. If you skip question i, you get to make the decision on the next question.

• For example, given questions = [[3, 2], [4, 3], [4, 4], [2, 5]]:
  • If question 0 is solved, you will earn 3 points but you will be unable to solve questions 1 and 2.
  • If instead, question 0 is skipped and question 1 is solved, you will earn 4 points but you will be unable to solve questions 2 and 3.

Return the maximum points you can earn for the exam.

 

Example 1:

Input: questions = [[3,2],[4,3],[4,4],[2,5]]
Output: 5
Explanation: The maximum points can be earned by solving questions 0 and 3.
- Solve question 0: Earn 3 points, will be unable to solve the next 2 questions
- Unable to solve questions 1 and 2
- Solve question 3: Earn 2 points
Total points earned: 3 + 2 = 5. There is no other way to earn 5 or more points.

Example 2:

Input: questions = [[1,1],[2,2],[3,3],[4,4],[5,5]]
Output: 7
Explanation: The maximum points can be earned by solving questions 1 and 4.
- Skip question 0
- Solve question 1: Earn 2 points, will be unable to solve the next 2 questions
- Unable to solve questions 2 and 3
- Solve question 4: Earn 5 points
Total points earned: 2 + 5 = 7. There is no other way to earn 7 or more points.

 

Constraints:

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

Accepted

8,683

Submissions

22,040

public long MostPoints(int[][] questions)
{
    long[] dp = new long[questions.Length];

    dp[dp.Length - 1] = questions[questions.Length - 1][0];
    for (int i = dp.Length - 2; i >= 0; i--)
        dp[i] = Math.Max(dp[i + 1], questions[i][0] + ((i + questions[i][1] + 1 < dp.Length) ? (dp[i + questions[i][1] + 1]) : 0));
    return dp[0];
}