Hotel

Define the subproblems for your solution.
1. Let F(j) be the minimum total penalty incurred for traveling from hotel_0 to hotel_1.

Give a recursive formulation to solve the subproblems. Include the base cases.

F(j) = min(F(i) + penalty(i, j)) for all i in range(0, j)

The base case is:

F(0) = 0 
# Since there's no penalty to start at hotel_0

Give pseudocode for a memoized, top-down algorithm that outputs this minimum.

Initialize an array memo of size n with -1
Define function F(j):
    if j == 0:
        return 0
    if memo[j] is not -1:
        return memo[j]
    min_penalty = MAX_INT # largest integer we can store
    for i from 0 to j-1:
        min_penalty = min(min_penalty, F(i) + penalty(i, j))
    memo[j] = min_penalty
    return memo[j]

Give pseudocode for an efficient, bottom-up algorithm that outputs this minimum.

Initialize an array dp of size n with MAX_INT
dp[0] = 0
for j from 1 to n-1:
    for i from 0 to j-1:
        dp[j] = min(dp[j], dp[i] + penalty(i, j))
return dp[n-1]

What is the runtime of your solution? Justify your answer.
1. The runtime for the bottom-up dynamic programming solution is O(n^2) where n is the number of hotels. This is because for each hotel j, we compute the minimum penalty by considering each possible previous hotel i, and there are n hotels to consider. Since we are doing this for every hotel from 1 to n-1, the overall complexity is quadratic.
1. The runtime for the memoized top-down approach is similar to the bottom-up approach, which is O(n^2), because in the worst case, every subproblem will be solved exactly once and each subproblem solution involves a linear scan through all previous hotels, which takes O(n) time. Thus, with n subproblems, this leads to O(n^2) overall time complexity. The advantage of memoization here is that it avoids recomputation of subproblems that are solved multiple times in the naive recursive approach.

Explain how to modify your algorithm to also output the optimal sequence of hotels.

To output the optimal sequence of hotels, we need to store the sequence of hotels that leads to the minimum penalty at each step. We can do this by maintaining a list or array that keeps track of the previous hotel for each dp[j].

Initialize an array dp of size n with infinity
Initialize an array prev of size n with -1
dp[0] = 0
for j from 1 to n-1:
    for i from 0 to j-1:
        if dp[j] > dp[i] + penalty(i, j):
            dp[j] = dp[i] + penalty(i, j)
            prev[j] = i
# To recover the optimal path, 
# we trace back from hotel_n-1 using the prev array.
Initialize an empty list path
current = n-1
while current != -1:
    path.insert(0, current)
    current = prev[current]
return path