homework.wenqian.dev
← Course materials

Tutorial 11 · Dynamic Programming

Recursion and memoization · LIS · LCS

Copy full template

Python 3. No additional packages. Save as dp_states.py; run python3 dp_states.py 2 to check Q2. On Windows, python3 can be replaced with py.

1. Recursive call count

Written

For the function below, calculate ways(4), the total number of calls, and the number of distinct n values. Include the initial call and base cases. Name one repeated call.

Input
n = 4; each move is 1 or 2 steps.
Output
The result, two counts, and one repeated call.

Example

plain
ways(0) = 1; ways(1) = 1

Template

python
def ways(n):    if n <= 1:        return 1    return ways(n - 1) + ways(n - 2)# ways(4) = ?# total calls = ?; distinct states = ?# Name one repeated state.

2. Climbing stairs: memoization

Coding

Implement stairs_memo(n) using recursion and a dictionary. Each move climbs 1 or 2 steps. Different orders count as different routes. For n=0, return 1.

Input
A nonnegative integer n.
Output
The number of routes to step n.

Example

plain
stairs_memo(5) → 8stairs_memo(0) → 1

Template

python
def stairs_memo(n):    # Q02: create memo once, outside the recursive helper.    # Cache by remaining steps; return the helper's result.    raise NotImplementedError("Q02")
Check: python3 dp_states.py 2
python
def check_q02():    assert [stairs_memo(n) for n in range(8)] == [1, 1, 2, 3, 5, 8, 13, 21]    assert stairs_memo(30) == 1346269    assert stairs_memo(3) == 3

3. Climbing stairs: DP table

Coding

Implement stairs_table(n) using a loop. Each move climbs 1 or 2 steps. Set table[0]=1 and explain the loop order.

Input
A nonnegative integer n.
Output
A list of route counts for steps 0 through n.

Example

plain
stairs_table(5) → [1, 1, 2, 3, 5, 8]

Template

python
def stairs_table(n):    # Q03: initialize the base case, then fill in dependency order.    raise NotImplementedError("Q03")
Check: python3 dp_states.py 3
python
def check_q03():    assert stairs_table(0) == [1]    assert stairs_table(1) == [1, 1]    assert stairs_table(6) == [1, 1, 2, 3, 5, 8, 13]

4. Blocked stairs

Debugging

Fix stairs_blocked(n, blocked). Each move climbs 1 or 2 steps. You may jump over a blocked step but cannot land on it. Step 0 is always usable.

Input
n ≥ 0; blocked is a set of step numbers from 1 to n.
Output
The number of routes that reach step n without landing on blocked steps.

Example

plain
stairs_blocked(4, {2}) → 1  # 0 → 1 → 3 → 4stairs_blocked(3, {3}) → 0

Code to fix

python
def stairs_blocked(n, blocked):    # Q04: this code is wrong. Repair its base cases and blocked states.    table = [1] * (n + 1)    for k in range(2, n + 1):        if k not in blocked:            table[k] = table[k - 1] + table[k - 2]    return table[n]
Check: python3 dp_states.py 4
python
def check_q04():    assert stairs_blocked(0, set()) == 1    assert stairs_blocked(1, {1}) == 0    assert stairs_blocked(2, {1}) == 1    assert stairs_blocked(4, {2}) == 1    assert stairs_blocked(5, {3}) == 2    assert stairs_blocked(3, {3}) == 0

5. LIS: calculate the table

Written

A subsequence keeps the original order and may skip elements. LIS is a longest strictly increasing subsequence. For the list below, calculate dp[i]: the longest length ending at index i. Give the overall length and explain why the input cannot be sorted first.

Input
values = [3, 1, 2, 5, 4, 6].
Output
The dp list, the LIS length, and an explanation.

Example

plain
[1, 2, 4, 6] is allowed; [1, 2, 3, 4, 5, 6] is not.

Template

python
values = [3, 1, 2, 5, 4, 6]# ending = ?# overall length = ?# Why is sorting invalid?

6. LIS: implement the table

Coding

Implement lis_ending(values). dp[i] is the length of the longest strictly increasing subsequence ending at index i. Return the full list in O(n²) time without changing values.

Input
A list of integers; an empty list is allowed.
Output
The dp list; return [] for empty input.

Example

plain
lis_ending([3,1,2,5,4,6]) → [1,1,2,3,3,4]lis_ending([2,2,2]) → [1,1,1]

Template

python
def lis_ending(values):    # Q06: one state per endpoint; compare all valid earlier endpoints.    raise NotImplementedError("Q06")
Check: python3 dp_states.py 6
python
def check_q06():    assert lis_ending([]) == []    assert lis_ending([2, 2, 2]) == [1, 1, 1]    assert lis_ending([9, 7, 5]) == [1, 1, 1]    assert lis_ending([1, 2, 3, 0]) == [1, 2, 3, 1]    values = [3, 1, 2, 5, 4, 6]    original = values[:]    assert lis_ending(values) == [1, 1, 2, 3, 3, 4]    assert values == original

7. LIS: return a subsequence

Coding

Implement lis_sequence(values) using lis_ending. Return the actual values of one longest strictly increasing subsequence, in their original order. Any optimal answer is accepted.

Input
A list of integers; an empty list is allowed.
Output
One LIS as a list; return [] for empty input.

Uses your Q06 function.

Example

plain
lis_sequence([3,1,2,5,4,6]) → [1,2,5,6] or [1,2,4,6]

Template

python
def lis_sequence(values):    # Q07: recover a path through the endpoint states.    raise NotImplementedError("Q07")
Check: python3 dp_states.py 7
python
def check_q07():    for values, length in [([], 0), ([2,2,2], 1), ([1,2,3,0], 3), ([3,1,2,5,4,6], 4)]:        original = values[:]        answer = lis_sequence(values)        assert len(answer) == length        assert all(x < y for x, y in zip(answer, answer[1:]))        stream = iter(values)        assert all(any(v == x for v in stream) for x in answer)        assert values == original

8. LIS: fix the returned length

Debugging

Fix lis_length(values). It must handle an empty list and a longest subsequence that ends before the last element. Give a counterexample to the supplied code.

Input
A list of integers.
Output
The LIS length; return 0 for empty input.

Uses your Q06 function.

Example

plain
lis_length([1,2,3,0]) → 3; lis_length([]) → 0

Code to fix

python
def lis_length(values):    dp = lis_ending(values)    # Q08: this return is wrong.    return dp[-1]
Check: python3 dp_states.py 8
python
def check_q08():    assert lis_length([]) == 0    assert lis_length([1,2,3,0]) == 3    assert lis_length([4,3,2]) == 1    assert lis_length([2,2,2]) == 1

9. LCS: calculate the table

Written

LCS is a longest subsequence common to two strings. Characters must stay in order but need not be adjacent. Let dp[i][j] be the LCS length of A[:i] and B[:j]. Fill the table below. Explain the zero row and why a mismatch uses max rather than addition.

Input
A = 'ABC', B = 'AC'.
Output
The completed table and explanations.

Example

plain
A[:2] = 'AB'; B[:1] = 'A'

Template

python
# Columns: empty, A, C# empty: [0, 0, 0]# A:     [0, ?, ?]# AB:    [0, ?, ?]# ABC:   [0, ?, ?]# State meaning: ...

10. LCS: implement the table

Coding

Implement lcs_table(a,b). Return the full LCS table, including the empty-prefix row and column. Each row must be a separate list.

Input
Two strings a and b.
Output
A (len(a)+1) × (len(b)+1) table.

Example

plain
lcs_table('ABC', 'AC')[-1][-1] → 2

Template

python
def lcs_table(a, b):    # Q10: base row/column = 0; then match or skip one ending character.    raise NotImplementedError("Q10")
Check: python3 dp_states.py 10
python
def check_q10():    assert lcs_table('', '') == [[0]]    assert lcs_table('AB', '') == [[0], [0], [0]]    assert lcs_table('ABC', 'AC') == [[0,0,0],[0,1,1],[0,1,1],[0,1,2]]    assert lcs_table('AB', 'BA')[-1][-1] == 1    assert lcs_table('ABCBDAB', 'BDCABA')[-1][-1] == 4    table = lcs_table('AA', 'A')    assert table[0] is not table[1]

11. LCS: return a subsequence

Coding

Implement lcs_sequence(a,b) using lcs_table. Return one longest common subsequence. Any optimal answer is accepted.

Input
Two strings a and b.
Output
One LCS string; return an empty string if there are no common characters.

Uses your Q10 function.

Example

plain
lcs_sequence('ABC', 'AC') → 'AC'lcs_sequence('AB', 'BA') → 'A' or 'B'

Template

python
def lcs_sequence(a, b):    # Q11: walk backward; reverse the collected characters at the end.    raise NotImplementedError("Q11")
Check: python3 dp_states.py 11
python
def check_q11():    for a, b, length in [('', 'ABC', 0), ('ABC','AC',2), ('AB','BA',1), ('ABCBDAB','BDCABA',4)]:        answer = lcs_sequence(a, b)        assert isinstance(answer, str) and len(answer) == length        for source in (a, b):            stream = iter(source)            assert all(any(c == x for c in stream) for x in answer)

12. LCS: fix the memo key

Debugging

Fix lcs_memo(a,b) while keeping its recursive structure. The current cache uses an incomplete key. The function must also handle an answer of 0.

Input
Two strings a and b.
Output
Their LCS length.

Example

plain
lcs_memo('ABC', 'AC') → 2lcs_memo('AB', 'CD') → 0

Code to fix

python
def lcs_memo(a, b):    memo = {}    def solve(i, j):        if i == 0 or j == 0:            return 0        # Q12: the cache key below is incomplete.        if i not in memo:            if a[i - 1] == b[j - 1]:                memo[i] = 1 + solve(i - 1, j - 1)            else:                memo[i] = max(solve(i - 1, j), solve(i, j - 1))        return memo[i]    return solve(len(a), len(b))
Check: python3 dp_states.py 12
python
def check_q12():    for a, b, expected in [('', '', 0), ('AB','CD',0), ('ABC','AC',2), ('ABCBDAB','BDCABA',4), ('ABBA','BAAB',2)]:        assert lcs_memo(a, b) == expected, (a, b)    assert lcs_memo('AAAA', 'AA') == 2    assert lcs_memo('X', 'Y') == 0

13. Count LIS solutions

Coding · Optional

Implement lis_count(values). Count the longest strictly increasing subsequences. Different index selections count separately, even when their values are the same.

Input
A list of integers.
Output
The number of longest subsequences; return 0 for empty input.

Example

plain
lis_count([1,3,5,4,7]) → 2lis_count([2,2,2]) → 3

Template

python
def lis_count(values):    # Q13: a better length replaces the count; an equal length adds to it.    raise NotImplementedError("Q13")
Check: python3 dp_states.py 13
python
def check_q13():    assert lis_count([]) == 0    assert lis_count([2,2,2]) == 3    assert lis_count([1,3,5,4,7]) == 2    assert lis_count([1,2,3]) == 1    assert lis_count([1,2,1,2]) == 3

14. Maximum-sum increasing subsequence

Coding · Optional

Implement max_sum_increasing(values). Maximize the sum of a strictly increasing subsequence. For nonempty input, choose at least one value, even if every value is negative.

Input
A list of integers.
Output
The maximum sum; return 0 for empty input.

Example

plain
max_sum_increasing([4,1,2,6]) → 10  # [4,6]max_sum_increasing([-3,-1]) → -1

Template

python
def max_sum_increasing(values):    # Q14: still end at i, but store sum rather than length.    raise NotImplementedError("Q14")
Check: python3 dp_states.py 14
python
def check_q14():    assert max_sum_increasing([]) == 0    assert max_sum_increasing([4,1,2,6]) == 10    assert max_sum_increasing([-3,-1]) == -1    assert max_sum_increasing([2,2]) == 2

15. Minimum deletions

Coding · Optional

Implement deletions_to_match(a,b). You may delete characters from either string, but cannot insert or replace them. Find the minimum total deletions needed to make the strings equal. Explain your formula.

Input
Two strings a and b.
Output
The minimum total number of deletions.

Uses your Q10 function.

Example

plain
deletions_to_match('sea', 'eat') → 2  # keep 'ea'

Template

python
def deletions_to_match(a, b):    # Q15: first find the longest sequence both strings can keep.    raise NotImplementedError("Q15")
Check: python3 dp_states.py 15
python
def check_q15():    assert deletions_to_match('sea', 'eat') == 2    assert deletions_to_match('', 'ABC') == 3    assert deletions_to_match('same', 'same') == 0    assert deletions_to_match('AB', 'CD') == 4

16. LCS: reduce the space usage

Coding · Optional

Implement lcs_length_small_space(a,b) using two rows. Use O(min(len(a),len(b))) auxiliary space and O(len(a)×len(b)) time. Explain why Q11 cannot directly backtrack using just these rows.

Input
Two strings a and b.
Output
Their LCS length.

Example

plain
lcs_length_small_space('ABCBDAB','BDCABA') → 4

Template

python
def lcs_length_small_space(a, b):    # Q16: use the shorter string for columns; rebuild the current row.    raise NotImplementedError("Q16")
Check: python3 dp_states.py 16
python
def check_q16():    assert lcs_length_small_space('', 'ABC') == 0    assert lcs_length_small_space('ABC', '') == 0    assert lcs_length_small_space('AA', 'A') == 1    assert lcs_length_small_space('ABCBDAB', 'BDCABA') == 4    assert lcs_length_small_space('ABCDE', 'ACE') == 3

Full template

Includes all functions and checks. Replace each function as you complete it. Q1, Q5, and Q9 are written questions; Q13–16 are optional.

python
# Tutorial 11 — DP state design# Python 3, standard library only. No installation beyond Python is needed.# Q01, Q05 and Q09 are written questions on the webpage.# Complete one function, then run: python3 dp_states.py 2# Q07/Q08 depend on Q06. Q11/Q15 depend on Q10.# The default command checks the nine core coding/debugging questions.def stairs_memo(n):    # Q02: create memo once, outside the recursive helper.    # Cache by remaining steps; return the helper's result.    raise NotImplementedError("Q02")def stairs_table(n):    # Q03: initialize the base case, then fill in dependency order.    raise NotImplementedError("Q03")def stairs_blocked(n, blocked):    # Q04: this code is wrong. Repair its base cases and blocked states.    table = [1] * (n + 1)    for k in range(2, n + 1):        if k not in blocked:            table[k] = table[k - 1] + table[k - 2]    return table[n]def lis_ending(values):    # Q06: one state per endpoint; compare all valid earlier endpoints.    raise NotImplementedError("Q06")def lis_sequence(values):    # Q07: recover a path through the endpoint states.    raise NotImplementedError("Q07")def lis_length(values):    dp = lis_ending(values)    # Q08: this return is wrong.    return dp[-1]def lcs_table(a, b):    # Q10: base row/column = 0; then match or skip one ending character.    raise NotImplementedError("Q10")def lcs_sequence(a, b):    # Q11: walk backward; reverse the collected characters at the end.    raise NotImplementedError("Q11")def lcs_memo(a, b):    memo = {}    def solve(i, j):        if i == 0 or j == 0:            return 0        # Q12: the cache key below is incomplete.        if i not in memo:            if a[i - 1] == b[j - 1]:                memo[i] = 1 + solve(i - 1, j - 1)            else:                memo[i] = max(solve(i - 1, j), solve(i, j - 1))        return memo[i]    return solve(len(a), len(b))def lis_count(values):    # Q13: a better length replaces the count; an equal length adds to it.    raise NotImplementedError("Q13")def max_sum_increasing(values):    # Q14: still end at i, but store sum rather than length.    raise NotImplementedError("Q14")def deletions_to_match(a, b):    # Q15: first find the longest sequence both strings can keep.    raise NotImplementedError("Q15")def lcs_length_small_space(a, b):    # Q16: use the shorter string for columns; rebuild the current row.    raise NotImplementedError("Q16")# Checks — keep below your functions.def check_q02():    assert [stairs_memo(n) for n in range(8)] == [1, 1, 2, 3, 5, 8, 13, 21]    assert stairs_memo(30) == 1346269    assert stairs_memo(3) == 3def check_q03():    assert stairs_table(0) == [1]    assert stairs_table(1) == [1, 1]    assert stairs_table(6) == [1, 1, 2, 3, 5, 8, 13]def check_q04():    assert stairs_blocked(0, set()) == 1    assert stairs_blocked(1, {1}) == 0    assert stairs_blocked(2, {1}) == 1    assert stairs_blocked(4, {2}) == 1    assert stairs_blocked(5, {3}) == 2    assert stairs_blocked(3, {3}) == 0def check_q06():    assert lis_ending([]) == []    assert lis_ending([2, 2, 2]) == [1, 1, 1]    assert lis_ending([9, 7, 5]) == [1, 1, 1]    assert lis_ending([1, 2, 3, 0]) == [1, 2, 3, 1]    values = [3, 1, 2, 5, 4, 6]    original = values[:]    assert lis_ending(values) == [1, 1, 2, 3, 3, 4]    assert values == originaldef check_q07():    for values, length in [([], 0), ([2,2,2], 1), ([1,2,3,0], 3), ([3,1,2,5,4,6], 4)]:        original = values[:]        answer = lis_sequence(values)        assert len(answer) == length        assert all(x < y for x, y in zip(answer, answer[1:]))        stream = iter(values)        assert all(any(v == x for v in stream) for x in answer)        assert values == originaldef check_q08():    assert lis_length([]) == 0    assert lis_length([1,2,3,0]) == 3    assert lis_length([4,3,2]) == 1    assert lis_length([2,2,2]) == 1def check_q10():    assert lcs_table('', '') == [[0]]    assert lcs_table('AB', '') == [[0], [0], [0]]    assert lcs_table('ABC', 'AC') == [[0,0,0],[0,1,1],[0,1,1],[0,1,2]]    assert lcs_table('AB', 'BA')[-1][-1] == 1    assert lcs_table('ABCBDAB', 'BDCABA')[-1][-1] == 4    table = lcs_table('AA', 'A')    assert table[0] is not table[1]def check_q11():    for a, b, length in [('', 'ABC', 0), ('ABC','AC',2), ('AB','BA',1), ('ABCBDAB','BDCABA',4)]:        answer = lcs_sequence(a, b)        assert isinstance(answer, str) and len(answer) == length        for source in (a, b):            stream = iter(source)            assert all(any(c == x for c in stream) for x in answer)def check_q12():    for a, b, expected in [('', '', 0), ('AB','CD',0), ('ABC','AC',2), ('ABCBDAB','BDCABA',4), ('ABBA','BAAB',2)]:        assert lcs_memo(a, b) == expected, (a, b)    assert lcs_memo('AAAA', 'AA') == 2    assert lcs_memo('X', 'Y') == 0def check_q13():    assert lis_count([]) == 0    assert lis_count([2,2,2]) == 3    assert lis_count([1,3,5,4,7]) == 2    assert lis_count([1,2,3]) == 1    assert lis_count([1,2,1,2]) == 3def check_q14():    assert max_sum_increasing([]) == 0    assert max_sum_increasing([4,1,2,6]) == 10    assert max_sum_increasing([-3,-1]) == -1    assert max_sum_increasing([2,2]) == 2def check_q15():    assert deletions_to_match('sea', 'eat') == 2    assert deletions_to_match('', 'ABC') == 3    assert deletions_to_match('same', 'same') == 0    assert deletions_to_match('AB', 'CD') == 4def check_q16():    assert lcs_length_small_space('', 'ABC') == 0    assert lcs_length_small_space('ABC', '') == 0    assert lcs_length_small_space('AA', 'A') == 1    assert lcs_length_small_space('ABCBDAB', 'BDCABA') == 4    assert lcs_length_small_space('ABCDE', 'ACE') == 3import sysCHECKS = {2: check_q02, 3: check_q03, 4: check_q04, 6: check_q06, 7: check_q07, 8: check_q08, 10: check_q10, 11: check_q11, 12: check_q12, 13: check_q13, 14: check_q14, 15: check_q15, 16: check_q16}GROUPS = {    "memo": [2, 3, 4],    "lis": [6, 7, 8],    "lcs": [10, 11, 12],    "extra": [13, 14, 15, 16],    "core": [2, 3, 4, 6, 7, 8, 10, 11, 12],    "all": sorted(CHECKS),}if __name__ == "__main__":    stage = sys.argv[1] if len(sys.argv) > 1 else "core"    if stage.isdigit() and int(stage) in CHECKS:        selected = [int(stage)]    elif stage in GROUPS:        selected = GROUPS[stage]    else:        print("Choose memo, lis, lcs, extra, core, all, or a coding question number.")        sys.exit(2)    for number in selected:        try:            CHECKS[number]()        except Exception as error:            print(f"Q{number:02d} failed: {type(error).__name__}: {error}")            print("Check this question and its listed dependencies, then try again.")            sys.exit(1)        print(f"Q{number:02d} passed.")    print(f"{stage}: {len(selected)}/{len(selected)} checks passed.")
bash
python3 dp_states.py       # Q2–4, Q6–8, Q10–12python3 dp_states.py extra # Q13–16python3 dp_states.py all   # all coding questions