Intuition
- This question is important for understanding the meaning of top vs down. In the case of questions like Climbing Stairs, I chose top as the top of the stair and bottom as the bottom of the stair. However, this is not the correct visualization.
- A better way of visualizing is thinking of whether the current subproblem relies on future subproblems or previous subproblems. In this case, the i + questions[i][1] + 1th question relies on information from the past (whether you picked the ith question).
- Therefore, top in this case is index 0, since recursion is the act of collecting information from the future based on current decisions.
- Bottom is the last index, since the last index is the beginning for collection of information that will be required for the past.
Complexity
Runtime
Space
Code
Bottom Up
class Solution:
def mostPoints(self, questions: List[List[int]]) -> int:
n = len(questions)
dp = defaultdict(int)
for i in reversed(range(n)):
points, skip = questions[i]
dp[i] = max(dp[i + 1], points + dp[i + skip + 1])
return dp[0]Top Down
class Solution:
def mostPoints(self, questions: List[List[int]]) -> int:
n = len(questions)
@cache
def r(i):
if i >= n:
return 0
points, skip_amt = questions[i]
return max(r(i + 1), points + r(i + skip_amt + 1))
return r(0)Code Which Does NOT Work
class Solution:
def mostPoints(self, questions: List[List[int]]) -> int:
@cache
def r(i):
if i < 0:
return 0
points, skip_amt = questions[i]
return max(r(i - 1), points + r(i - skip_amt - 1))
return r(len(questions) - 1)- Since we rely on skipping future information.
Notes
Cards
START Basic Front: Solving Questions With Brainpower Back: Top is the end, and bottom is the beginning, since you rely on information from the past. END