Advance Dynamic Programming States

Practice Exercise Interview Easy Dynamic Programming

Checking your account…

Loading the interactive Practice workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Practice workspace

Problem

Implement non_adjacent_prefix_states(values) for nonnegative integers. Return a list of length len(values) + 1 where state i is the largest sum selectable from values[:i] without choosing adjacent positions. State 0 must be 0.

Starter code

def non_adjacent_prefix_states(values):
    pass

Test cases

alternating-choices

{
  "args": [
    [
      2,
      7,
      9,
      3,
      1
    ]
  ]
}

Expected: [0,2,7,11,11,12]

two-values

{
  "args": [
    [
      5,
      1
    ]
  ]
}

Expected: [0,5,5]

Wizard outline

Step 1: Seed the empty-prefix optimum
Create states with state 0 equal to 0. Selecting from zero values has optimum zero and anchors every later prefix index.
Step 2: Carry equal zero optima
Append one state per zero value without changing the optimum. A zero may be skipped or selected with the same score; either way the prefix optimum remains zero.
Step 3: Choose across the first two values
Record the first value, then keep the larger of the first two because they are adjacent. For two adjacent values, a valid selection may take either one but not both.
Step 4: Apply the skip-versus-take recurrence
For each prefix, compare the previous optimum with the two-back optimum plus the current value. Skipping keeps state i - 1; taking forbids the previous value and therefore combines with state i - 2.

Footguns and prerequisites

Adding the current value to the immediately previous state can select adjacent positions.
Returning only the final optimum omits the requested transition history.
dynamic programming

Reviewed references

Python More on Lists

Prepared Interview Problems

House Robber(opens in a new tab)
Advance Dynamic Programming States isolates state[i] is the optimum over exactly the first i values, whether the i-th value is skipped or selected. That focused state discipline is required when implementing house robber as a complete Interview Problem.
House Robber II(opens in a new tab)
Advance Dynamic Programming States isolates state[i] is the optimum over exactly the first i values, whether the i-th value is skipped or selected. That focused state discipline is required when implementing house robber two as a complete Interview Problem.
Target Sum(opens in a new tab)
Advance Dynamic Programming States isolates state[i] is the optimum over exactly the first i values, whether the i-th value is skipped or selected. That focused state discipline is required when implementing target sum as a complete Interview Problem.

Recommended approach and implementation

When choosing the current item forbids only the immediately previous item, the optimum depends on two earlier prefix states. state[i] is the optimum over exactly the first i values, whether the i-th value is skipped or selected.

Why it works: For each prefix, every valid solution either skips the newest value and uses state[i-1], or selects it and combines with state[i-2]. Taking the better exhaustive case proves the final state is optimal.

def non_adjacent_prefix_states(values):
    states = [0]
    previous_two = 0
    previous_one = 0
    for value in values:
        current = max(previous_one, previous_two + value)
        states.append(current)
        previous_two, previous_one = previous_one, current
    return states