One-dimensional DP in Python: house robber, coin change, LIS

Why it matters

Many dynamic programming problems have a state that is a single number: a position in a row, a day in a timeline, or an amount of money. When the state is one number, the table is one row. That makes these problems the best place to practise the recipe from the last lesson, because you can print the whole table and check every cell. Interviewers use them often, and the thinking you learn here carries over to two-dimensional problems later in the module.

This lesson covers three problems. In the house robber problem you choose which items to take, with a neighbour rule. In coin change you find the fewest coins that make an exact amount. In the longest increasing subsequence (LIS) you find the longest ordered run of numbers that goes up. Each one has a different shape, so together they show you three ways to write a one-row table.

You should have finished the first lesson. You should know what a state, a recurrence, a base case and a loop order are. The programs here are plain Python files. The ones marked python run print their output without reading input. Where a program reads input, the lesson tells you exactly what to type when you run it.

The house robber problem

Picture a street of houses. Each house holds some money. A thief wants to rob houses, but an alarm links each house to the next one, so robbing two houses in a row sets off the alarm. The thief can rob any set of houses where no two are next to each other. The question is: what is the most money the thief can take?

Take a small street with values 2, 7, 9, 3, 1, from left to right. You could rob houses 1, 3 and 5 for 2 + 9 + 1 = 12. You could rob houses 2 and 4 for 7 + 3 = 10. You could rob houses 2 and 5 for 7 + 1 = 8. The best is 12. A brute-force program would try every subset that obeys the neighbour rule. That grows quickly with the number of houses. We want something that takes one pass.

The idea in plain words

Walk down the street one house at a time. At each house you face a decision that depends only on what you did at the previous house. Either you rob this house, which means you must not have robbed the house just before it. Or you skip this house, which leaves you free to have robbed the previous one. So after each house we need to remember two numbers.

• take: the most money you can have if you robbed the current house.
• skip: the most money you can have if you did not rob the current house.

The state is therefore "where am I on the street, and did I rob this house". Each house gives one pair of numbers, and the pair for house i depends only on the pair for house i - 1. That is why the table has one row and why two variables are enough.

The recurrence

Let x be the value of the current house. Here are the two new numbers.

• If you rob the current house, you add x to the best total from the house before, when that house was skipped. So new_take = skip + x.
• If you skip the current house, you take the better of the two old numbers, because either choice for the previous house is allowed. So new_skip = max(skip, take).

The base cases come from an empty street. Before the first house, take = 0 and skip = 0, because you have robbed nothing. The answer for the whole street is the bigger of the two numbers after the last house, because the last house may or may not be robbed.

A worked trace

Here is the full trace for 2, 7, 9, 3, 1. Each row shows the values after one house. Read across the row and check each cell against the rule above.

The answer is max(12, 11) = 12. The code below does exactly this trace. Notice the order inside the loop. The code computes new_take first, because it needs the old skip. Then it updates skip, which needs the old take. Then it updates take. Swapping those steps is a common bug, which the common mistakes section shows.

The same idea as a table

Some people find it easier to see the full table with one cell per house, because the table is what the recipe describes. Keep the best answer for the street up to house i in dp[i]. The choice is then "rob house i and add dp[i - 2], or skip it and keep dp[i - 1]". Both forms give the same answers. The two-variable form uses less memory. In an interview, write the table form first, because it shows the recipe clearly, and then mention that the table only needs two cells.

dp[i] = max(dp[i - 1], dp[i - 2] + value[i])

Read the formula slowly. dp[i - 1] means "skip house i and keep the best for the houses before it". dp[i - 2] + value[i] means "rob house i, which forces house i - 1 to stay alone, so add to the best for the houses up to i - 2". The formula is the same recurrence written with one number per house.

The code for house robber

The next program does not read input. It runs the trace from the last section, printing the two numbers after each house, and then checks a few small streets.

The output is:

start take=0 skip=0
house 2: take=2 skip=0
house 7: take=7 skip=2
house 9: take=11 skip=7
house 3: take=10 skip=11
house 1: take=12 skip=11
12
0 5 10

The first line of the program defines rob, which is the version you would hand in. The second function, rob_trace, is the same code with a print added, so you can compare each line with the table.

The next program reads the number of houses and their values from the input. Type these two lines when it asks for input:

5
2 7 9 3 1

def rob(nums):
    take = 0
    skip = 0
    for x in nums:
        new_take = skip + x
        skip = max(skip, take)
        take = new_take
    return max(take, skip)
 
 
n = int(input())
houses = [int(x) for x in input().split()]
print(f"maximum: {rob(houses)}")

The output is:

maximum: 12

The function input() waits for one line of text and returns it as a string. int(...) turns text into a whole number. input().split() cuts a line at the spaces, so "2 7 9 3 1" becomes the list of strings ["2", "7", "9", "3", "1"]. The list comprehension [int(x) for x in ...] turns each piece into a number. The variable n is the house count, which this version reads but does not need, because the second line already has the values. If you type fewer numbers than the count says, the program does not notice, so check the count yourself.

Edge cases for house robber

Think about the smallest streets before you trust the code. An empty street returns 0, because the loop does not run and both variables stay 0. A street with one house returns that house's value, because take becomes the value and skip stays 0. A street of two houses returns the larger value, not the sum, because the neighbour rule forbids taking both. The line print(rob([]), rob([5]), rob([3, 10])) in the program above checks these three cases. If the code gives the right answer for these, the base cases are right.

Negative values do not appear in the standard problem, since money cannot be negative. If a version of the problem allowed negative values, you would have to think about whether it is ever worth taking a house, and the recurrence would change. Read the statement, and do not assume.

Coin change: the fewest coins

Now a problem where the state is an amount rather than a position. You are given coin values, for example 1, 3 and 4, and a target amount, for example 6. You must make exactly the target using the fewest coins. You may use as many coins of each value as you like. If the amount cannot be made, the answer is -1.

Think about a shop clerk making change. The clerk wants to give exactly 6 units back using the fewest coins. The clerk might grab the largest coin first, which is 4, then two 1s. That is three coins. But using 3 and 3 gives the same amount with two coins. The greedy habit of taking the largest coin first is wrong here, and this is why coin change is a DP problem. The last module on greedy algorithms showed when greedy works. Here it does not.

State, recurrence and base case

State: dp[i] is the fewest coins that add up to exactly i. Recurrence: to make amount i, look at the last coin you added. It has some value c from the list of coins, and c must not be bigger than i. The remaining amount i - c must have been made with dp[i - c] coins. So the total is dp[i - c] + 1. Try every coin and keep the smallest result:

dp[i] = min over all coins c with c <= i of (dp[i - c] + 1)

Base case: dp[0] = 0, because making amount 0 needs no coins.

Unreachable amounts need a marker. If no coin combination makes amount i, the cell must say so. The usual choice is amount + 1. A real answer can never be more than amount coins, because the smallest coin is at least 1. So amount + 1 is bigger than any real answer and means "not reachable". The table starts with every cell set to this marker, and only reachable cells are lowered.

Why not use a very large number such as float("inf")? Python can use it, and it works here. The reason to use amount + 1 in this course is that it is an ordinary whole number with a clear meaning: no real answer can reach it. In languages with fixed-size integers, a huge marker such as the largest int breaks when 1 is added to it, because the value wraps around. Python does not wrap, but the habit of a marker that is safe to add to still makes the code portable.

A trace for coins 1, 3, 4 and amount 6

Fill the table from left to right. Each cell uses cells to its left, which are already final.

The answer is dp[6] = 2, from the two coins 3 and 3. The table as a row is 0 1 2 1 1 2 2.

What to watch for: a cell is final as soon as it is written, because all the cells it reads are already final. That is why the loop goes from 1 up to the amount. If the loop went the other way, the code would read cells that are still at the marker value.

The code for coin change

The program below reads the number of coins, the coin values and the amount. It uses the same table as the trace above. The loop over coins is inside the loop over amounts, so each cell tries every coin. Type these three lines when it asks for input:

3
1 3 4
6

def min_coins(coins, amount):
    dp = [amount + 1] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for c in coins:
            if c <= i and dp[i - c] + 1 < dp[i]:
                dp[i] = dp[i - c] + 1
    if dp[amount] > amount:
        return -1
    return dp[amount]
 
 
k = int(input())
coins = [int(x) for x in input().split()]
amount = int(input())
print(min_coins(coins, amount))

The output is:

2

Now test the impossible case. Run the program again and type these three lines:

1
2
3

The output is -1, because you cannot make 3 from coins of value 2 alone. The first line says there is 1 coin, the second line gives its value, and the third line is the amount.

Read the line if c <= i and dp[i - c] + 1 < dp[i]: carefully. The first test stops the program from reading dp[i - c] when c is bigger than i, because that would be a negative index. Python would not raise an error here. It would quietly read from the end of the list, which gives a wrong answer with no message. The second test keeps the smallest count. Together they implement the min in the recurrence. Python's and only runs the second part when the first part is true, so the first test protects the second.

Printing the table to see the values

The fastest way to learn a table is to print it. The next program does not read input. It prints the coin change table for two cases: one where every amount is reachable, and one where some amounts are not. Read the output and check it against the marker rule.

The output is:

coins {1, 3, 4}, amount 6:
[0, 1, 2, 1, 1, 2, 2]
coins {2}, amount 3:
[0, 4, 1, 4]

In the second table the marker is 4, which is amount + 1 for amount 3. Cell 1 is 4 because 1 cannot be made from coins of 2. Cell 3 is 4 for the same reason. Cell 2 is 1, because one coin of value 2 makes 2. The final answer is cell 3, which holds the marker, so the function returns -1.

The list [amount + 1] * (amount + 1) makes a new list of equal values. Each number in it is a separate int object, so changing one cell does not change the others. That is safe for numbers. The same expression with a list inside, such as [[]] * 3, would put the same inner list in all three positions, so a change to one would appear in all three.

Longest increasing subsequence

The third problem is about order, not money. Given a list of numbers, find the length of the longest subsequence that goes strictly up. A subsequence keeps the order of the original list but may skip some items. The numbers do not need to be next to each other. That is the difference from a subarray, which must be a continuous piece of the list.

Take the list 10, 9, 2, 5, 3, 7, 101, 18. One increasing subsequence is 2, 3, 7, 101. Another is 2, 5, 7, 18. No subsequence has length 5, so the answer is 4. Notice that 10, 101 is also increasing, but it is shorter. Notice too that 2, 3, 7, 101 skips the 5 and the 18. Skipping is allowed.

The state: ends at this index

Here is the hardest part of the problem, so take it slowly. We could define the state as "the longest increasing subsequence in the first i numbers". But that does not tell us how to add the next number, because the next number must be bigger than the last number used. So we define the state more tightly.

State: dp[i] is the length of the longest increasing subsequence that ends at index i, meaning its last number is nums[i].

Recurrence: look at every earlier index j where nums[j] < nums[i]. You can append nums[i] to any increasing subsequence that ends at j. So dp[i] = 1 + max(dp[j]) over those j. If no earlier number is smaller, the subsequence is just nums[i] by itself, so dp[i] = 1.

Base case: every cell starts at 1, because one number is always an increasing subsequence of length 1.

Answer: this is the step beginners miss. The longest subsequence can end at any index, not necessarily the last one. So the answer is the largest value in the whole dp list. If you return dp[n - 1], you may return a shorter answer when the longest run ends early.

A trace for the example list

Here is the trace. The column for j lists the earlier smaller numbers that can be extended.

The full list is [1, 1, 1, 2, 2, 3, 4, 4]. The largest value is 4, so the answer is 4. The last cell is also 4 here by chance. Try a list like 3, 4, 1 to see the difference: dp is [1, 2, 1], the answer is 2, and the last cell says 1.

The code for LIS

The program below reads a list of numbers, computes the table and prints the length. It uses two nested loops. The outer loop visits each index, and the inner loop looks back at every earlier index. That is the source of the time cost. Type these two lines when it asks for input:

8
10 9 2 5 3 7 101 18

def lis(nums):
    n = len(nums)
    dp = [0] * n
    best = 0
    for i in range(n):
        dp[i] = 1
        for j in range(i):
            if nums[j] < nums[i] and dp[j] + 1 > dp[i]:
                dp[i] = dp[j] + 1
        best = max(best, dp[i])
    return best
 
 
n = int(input())
nums = [int(x) for x in input().split()]
print("LIS length:", lis(nums))

The output is:

LIS length: 4

The variable best holds the running maximum. It is updated after each index, so at the end it holds the largest value in dp. That is the answer rule in code. The program never returns dp[n - 1].

The next program prints the dp list itself, so you can compare it with the trace above. It does not read input.

The output is:

dp = [1, 1, 1, 2, 2, 3, 4, 4]
answer = 4

This matches the trace. Cell 5 holds 3, because 2, 3, 7 ends at 7, which is index 5. Cells 6 and 7 both hold 4. The first holds 2, 3, 7, 101 and the second holds 2, 3, 7, 18.

Strictly increasing and the < sign

The code uses nums[j] < nums[i], which means strictly less. Equal values do not extend a run. If the problem asks for a non-decreasing subsequence, the test would become nums[j] <= nums[i]. Read the statement and copy the comparison exactly. Changing one sign changes the answer for lists with repeated numbers. For 2, 2, 2 the strict answer is 1 and the non-decreasing answer is 3. The program below shows both.

The output is:

strict: 1 [1, 1, 1]
non-decreasing: 3 [1, 2, 3]

The faster version, in words

The table version costs time O(n^2). The notation means the time grows with the square of n, because the inner loop can run up to n times for each of the n indexes. For n = 1000 that is about half a million steps, which is fast. For n = 100000 it is about five billion, which is too slow.

A faster version runs in O(n log n) time. It keeps a list of the smallest possible last value for each length of increasing subsequence, and uses binary search (checking the middle of a sorted list and halving the range each time) to place each new number. Python's bisect module provides the binary search. The function bisect_left(tails, x) returns the position where x would go in the sorted list tails.

The output is:

4
4

The length is right, but the list tails is not the subsequence itself. Its values are the smallest possible last numbers for each length, so the list can contain numbers that are not part of one single increasing run. Use the length as the answer, and use the table version when you need to explain each step. You do not need to write this version today. Know that it exists, know that it uses binary search, and know that the table version is the one you can explain step by step. Interviewers often ask for the table version first, then ask whether it can be faster.

What happens inside the program

When lis runs, Python keeps the list dp in memory as one object that holds n references to integer objects. Each access dp[j] is a quick lookup by position. That is why reading an earlier cell costs the same no matter how far back it is.

The two loops run in a fixed order. The outer loop index i moves from 0 to n - 1. For each i, the inner loop index j moves from 0 to i - 1. When the code reads dp[j], index j is always smaller than i, so dp[j] was written in an earlier outer step and holds its final value. This is the same guarantee you saw with Fibonacci.

The variable best is a local name inside the function lis. It is updated after each outer step. When the function returns, its value is handed back to the caller. The local names are removed at that point, and the list dp is also released, because nothing refers to it any more. Python frees the memory when the last reference goes away.

Common mistakes

Mistake 1: returning dp[n - 1] for LIS. The longest subsequence can end anywhere. Test it with 3, 4, 1. The last cell is 1, but the answer is 2. Always return the maximum of the table.

Mistake 2: using a marker that cannot be added to safely. In coin change, the code adds 1 to the marker. In a language with fixed-size integers, the largest value of the type plus 1 wraps around to a very negative number. The minimum then picks this negative number, and the answer is wrong. Python does not wrap around, so this mistake does not show up here, but the rule still holds for ports of this code. Use amount + 1, which is safe in every language.

Mistake 3: swapping the two updates in house robber. If you write take = skip + x and then skip = max(skip, take), the second line uses the new take, which is wrong. The skip value must use the old take. Compute new_take first, then update skip, then update take.

Mistake 4: confusing a subsequence with a subarray. A subarray is a continuous slice. The list 2, 9, 3, 4 has the subarray 3, 4, which is increasing and length 2. The subsequence 2, 3, 4 is longer, because it skips the 9. Problems use the words exactly, so read them carefully.

Mistake 5: forgetting that house robber cannot take two neighbours. Writing dp[i] = dp[i - 1] + x allows neighbours. The recurrence must use the house two steps back, or the variable that means "skipped the previous house".

Mistake 6: input that runs out. If the program asks for more lines than you typed, Python stops with an error. The program below reads one number per line, and it was given only the count and one value.

n = int(input())
houses = [int(input()) for _ in range(n)]
print(houses)

With the input 5 and then 2, the program stops with this message at the end of the traceback:

EOFError: EOF when reading a line

The message means the program asked for another line, and the input had none left. The traceback lines above it show the line in your own code that asked, which is the input() inside the list comprehension. Count the lines in your input against the count on the first line. The program in the coin change section reads its numbers from one line with split(), so a short line gives a different problem: the list is simply shorter than expected.

Mistake 7: a word that is not a number. If the input says five where the program expects an integer, int() stops with this message at the end of the traceback:

ValueError: invalid literal for int() with base 10: 'five'

Type the number as digits.

Debugging a one-dimensional table

When a one-row table gives a wrong answer, do three things in order. First, pick the smallest input where you know the right answer, such as an empty list, a list of one number, or an amount of 0. Second, print the whole list. Third, compare each cell with the value you worked out on paper, from left to right. The first cell that differs points to the bug, because every later cell depends on it.

Here is a real example. A student wrote the LIS loop but changed the comparison to nums[j] <= nums[i] by mistake. For the list 2, 2, 2 the student expected 1 and got 3. Printing the list gives [1, 2, 3]. Cell 1 is already 2, which is wrong, because the two 2s are equal and should not extend each other. The first wrong cell is cell 1, and the comparison in the inner loop is the cause.

Edge cases you should test

• House robber: an empty list gives 0, one house gives its value, two houses give the larger value.
• Coin change: an amount of 0 gives 0 coins, and an impossible amount gives -1.
• LIS: an empty list gives 0, one number gives 1, and a list that goes down the whole way gives 1.
• LIS with repeated numbers: check the strict comparison against the problem statement.

A good habit is to write these tests as comments before you write the code, and to check them by hand after. Interviewers like candidates who name the edge cases before the code.

Interview questions you should expect

"Why is the house robber solution O(1) space?" Because each new pair of numbers depends only on the previous pair. Two variables hold the whole state, so the memory does not grow with the number of houses. Time is O(n).

"Why does coin change need DP and not greedy?" Because the choice of the largest coin first can lead to a worse total. The example with coins 1, 3 and 4 and amount 6 shows it: greedy gives 3 coins and the optimum is 2. Name the counterexample. A strong answer names a counterexample instead of saying "greedy might fail".

"What is the time for coin change?" It is O(amount * number of coins), because each of the amount + 1 cells tries every coin once. Space is O(amount).

"What is the time for LIS, and how would you make it faster?" The table version is O(n^2). The faster version is O(n log n) and uses binary search over a list of smallest tail values. Say that you would work out the faster version on paper before coding it, since it is a little tricky.

Practice

Write each answer by hand first, then check with the programs in this lesson. Hidden solutions follow each question.

Exercise 1 (easy). Trace the house robber method on 1, 2, 3, 1 and give the take and skip values after each house. What is the answer?

Show the answer

Start take = 0, skip = 0. House 1 (value 1): new_take = 0 + 1 = 1, skip = max(0, 0) = 0, take = 1. House 2 (value 2): new_take = 0 + 2 = 2, skip = max(0, 1) = 1, take = 2. House 3 (value 3): new_take = 1 + 3 = 4, skip = max(1, 2) = 2, take = 4. House 4 (value 1): new_take = 2 + 1 = 3, skip = max(2, 4) = 4, take = 3. The answer is max(3, 4) = 4, which is houses 1 and 3 (1 + 3).

Exercise 2 (easy). Find the fewest coins for amount 11 with coins {2, 5}. If the amount cannot be made, say so.

Show the answer

Eleven is odd, so at least one 5 is needed. Using two 5s gives 10, and 1 is not a multiple of 2, so that fails. Using one 5 leaves 6, which is three 2s. So 5 + 2 + 2 + 2 uses 4 coins. The answer is 4. The table agrees: dp[11] = 4.

Exercise 3 (easy). Write the dp list of coin change for coins {2} and amount 4. Which cells mark the impossible amounts?

Show the answer

dp = [0, 5, 1, 5, 2], where 5 is amount + 1 for amount 4. Cells 1 and 3 are impossible, so they keep the marker. Cell 2 is 1 coin and cell 4 is 2 coins.

Exercise 4 (medium). For the list 3, 1, 4, 1, 5, 9, 2, 6, compute the LIS dp list by hand and give the answer.

Show the answer

dp for indexes 0 to 7 is [1, 1, 2, 1, 3, 4, 2, 4]. Index 0 (value 3) is 1. Index 1 (value 1) has no smaller earlier value, so 1. Index 2 (value 4) extends value 3 (dp 1), so 2. Index 3 (value 1) has no smaller earlier value, so 1. Index 4 (value 5) extends the best smaller earlier value, 4 (dp 2), so 3. Index 5 (value 9) extends 5 (dp 3), so 4. Index 6 (value 2) extends only the 1s (dp 1), so 2. Index 7 (value 6) extends 5 (dp 3), so 4. The answer is the maximum, 4.

Exercise 5 (medium). Explain in two sentences why the coin change inner loop must check c <= i before it reads dp[i - c].

Show the answer

If c is bigger than i, then i - c is negative, and Python reads a negative index from the end of the list. That gives a value from the wrong part of the table, with no error. The check stops the read, so the code only looks at valid cells.

Exercise 6 (medium). Modify the LIS function so it also returns the index where the answer's subsequence ends. What index does it return for the example list?

Show the answer

Track the index as well as the value. Keep best_index, and inside the outer loop write if dp[i] > best: best = dp[i]; best_index = i. For the example list the largest value 4 first appears at index 6, so best_index is 6. The subsequence 2, 3, 7, 101 ends there.

Exercise 7 (medium). Write the house robber recurrence in table form, using dp[i] for the best total over the first i houses, and check it on 2, 7, 9, 3, 1.

Show the answer

dp[0] = 0, dp[1] = value[1], and for i at least 2, dp[i] = max(dp[i - 1], dp[i - 2] + value[i]). For 2, 7, 9, 3, 1: dp = [0, 2, 7, 11, 11, 12]. The last cell is 12, matching the two-variable trace.

Exercise 8 (hard). Prove by example that greedy coin change, which always takes the largest coin that fits, fails for coins {1, 3, 4} and amount 6. Then find one amount with those coins where greedy is still optimal.

Show the answer

Greedy takes 4 first (the largest coin that fits 6), then 1 and 1, which is 3 coins. The optimum is 3 and 3, which is 2 coins, so greedy fails. A case where greedy works is amount 5 with coins {1, 3, 4}: greedy takes 4, then 1, which is 2 coins. No single coin makes 5, so 2 is the best possible, and greedy is optimal here.

Exercise 9 (hard). Explain why the answer for LIS is not always dp[n - 1], and describe a list of length 4 where the answer appears before the last index.

Show the answer

The longest increasing subsequence can end at any index, because a later number may be smaller than the end of the best run. For the list 1, 2, 3, 0, the dp list is [1, 2, 3, 1]. The longest run 1, 2, 3 ends at index 2, while the last index has dp 1, because 0 is smaller than every earlier number. So dp[n - 1] would return 1, but the answer is 3, the maximum.

What you now know

• A one-dimensional DP table has one state per index or amount, and each cell reads earlier cells.
• House robber keeps two numbers, "taken" and "skipped", and needs no list.
• Coin change uses amount + 1 as the unreachable marker, and the answer is -1 when the marker survives.
• LIS uses a state that means "ends at this index", and the answer is the maximum over the whole table.
• Greedy choices can fail on coin change, so the DP table is the safe method.
• When a table is wrong, print it, find the first wrong cell, and fix the rule that wrote it.