I recently attended a tech OA interview and stumbled upon this question.
I am able to come up with the Top Down memoization approach myself. But I am struggling to get the Bottom up code for the same problem even though I am able to figure out the recurrence relation.

Question:

Maximum Reachable index
There is an infinite array of integers numbered consecutively from 0.
At each step, a pointer can move from index i to index i+j, or remain where it is.
The value of i begins at 0. The value of j begins at 1 and at each step, j increments by 1.
There is one known index that must be avoided called badIndex.
Determine the highest index that can be reached in a given number of steps.
Example
steps = 4 badElement = 6
The pointer is limited to 4 steps and should avoid the bad item 6.

• Scenario 1:

• In the first step, i starts at 1. Move 1 unit to index 0+1=1 and j = 2.

• At step 2, move 2 units to index 1+2=3, and j = 3.

• At step 3, do not move. Otherwise, the pointer will move 3 units to the bad item 6. Now j = 4.

• At step 4, move 4 units to item 3 + 4 = 7.

• Scenario 2:

At step 1, remain at index 0. Now j = 2.

• At step 2, move 2 units to index 0+2=2 and j = 3.

• At step 3, move 3 units to index 2+3=5 and j = 4

• At step 4, move 4 units to index 5+4=9

So the answer, the maximum reachable index is 9

My Top Down Approach code:

class Solution:
        def maxIndexAvoidingBadIndex(self, steps, badIndex) -> int:
            memo = {}
            def dfs(i, j):
                # Base cases
                if i == badIndex:
                    return 0
                if j == steps + 1:
                    return i
    
                if (i, j) in memo:
                    return memo[(i, j)]
    
                result = max(dfs(i + j, j + 1), dfs(i, j + 1))
                memo[(i, j)] = result
                return result
    
            return dfs(0, 1)

I need help in understanding how to derive the bottom up tabulation solution for this one, thanks!
I am just also pasting the bottom up code, that I have in mind right now even though it’s not the right one, just for the reference.

def maxIndexAvoidingBadIndex_BU(self, steps, badIndex):
        dp = [0] * (steps + 2)
        
        dp[0] = 0
        for j in range(1, len(dp)):
            if j + dp[j - 1] != badIndex:
                dp[j] = max(j + dp[j - 1], dp[j - 1])
        
        print(dp)
        return dp[-1]