# Solving Questions with Brainpower

## Transitions

For question `i`, either:

1. Solve the question, gain the points, and only be able to answer the `i + cooldown` problem onwards
2. Skip the question

## Top-down

```python
def brainpower(questions):
    def solve(i):
        if i >= len(questions): return 0
        return max(solve(i + 1), solve(i + questions[i][1] + 1) + questions[i][0])
    return solve(0)
```

The recurrence relation, much like other [](https://interviews.woojiahao.com/problems-guide/dynamic-programming-roadmap/linear-sequence "mention") problems is obtained by directly mapping the transitions.

$$
dp(i) = \begin{cases}
0, i \geq |q|\\
\max(dp(i+1), dp(i+q\[i]\[1]+1)  +q\[i]\[0])
\end{cases}
$$

## Bottom-up

The recurrence is the same as the top-down approach as we need to have information about the "next" state, so prefixes will not be an ideal solution for this.

This means we will have to iterate from the back. We also add a padding of `0` towards the end of the array to represent the case when `i + 1` or `i + questions[i][1] + 1` exceed `N` (length of questions).

{% hint style="success" %}
**Trick:** Boundary conditions\
\
Very often you will encounter state transitions that can cause out of bounds such as `i + 1 >= N` above. In these scenarios, you can introduction boundary conditions by modifying the `dp` array to include additional leading/trailing elements.\
\
If the state transition may go *very* out of bounds like `i + questions[i][1] + 1`, then you can use `min(transition, N)` to default it to use the boundary condition.\
\
The value of the boundary condition is often the case when there is nothing to process. In this case, we add `0` as that's the default value that exists when there's "no questions".
{% endhint %}

```python
def brainpower(questions):
    N = len(questions)
    dp = [0] * (N + 1)
    for i in range(N - 1, -1, -1):
        dp[i] = max(dp[i + 1], dp[min(i + questions[i][1] + 1, N)] + questions[i][0]) 
    return dp[0]
```

## Further discussion

Actually, there is a way to implement the bottom-up solution using the "re-framing the problem" trick.

> Given that we want to solve question `i`, what's the maximum points achievable?

By thinking of the problem this way, we can devise an approach to figure out how to forcibly "solve" question `i`. We can iterate through `0..i-1` to find all days where we would have solved it and the cooldown does not exceed `i`. This results in the following recurrence instead:

$$
dp(i) = \max(q\[i]\[0], \forall j \in \[0, i), j + q\[j]\[1] < i \land dp(j) + q\[i]\[0])
$$

The reason we do not take $$dp(i - 1)$$ is because if $$dp(i - 1)$$ is chosen, we might not be able to solve question `i`. The only problem with this solution is that it takes $$O(n^2)$$ time to compute which does not fit within the constraints of the problem.

However, I would like to bring this up as an alternative thought process to highlight how sometimes "re-framing" the problem might not always be the optimal solution.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://interviews.woojiahao.com/problems-guide/dynamic-programming-roadmap/linear-sequence/solving-questions-with-brainpower.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.