Dynamic Programming

Dynamic programming solves problems through smaller subproblems while storing intermediate results.

It is especially useful when a problem has:

  • optimal substructure: the optimal solution can be efficiently obtained from the optimal solution of its subproblems.

  • overlapping subproblems: some subproblem solution are required in many other solution.

Memoization

Caching a costly tp obtain information means to store this information so that you can retrieve it cheaply later. Memoization is a specific kind of caching: caching the results of function calls, usually to avoid recomputing the same subproblem. Memoization is one technique to dramatically speed up a calculation with overlapping subproblems. The trade-off is that the results are kept in memory.

The recursive Fibonacci definition repeatedly requests identical values:

(1)\[\begin{split}\begin{cases} \mathcal{F}(n) = n & \textrm{if} ~ n \leq 1 \\ \mathcal{F}(n) = \mathcal{F}(n-1) + \mathcal{F}(n-2) & \textrm{otherwise} \end{cases}\end{split}\]

For example, computing a larger Fibonacci value may repeat several different recursive branches. Without memoization, identical computations are repeated. With memoization, every distinct Fibonacci state is computed once.

fibonacci_dependencies

Fibonacci dependencies up to F(6)

The previous figure represents the dependencies for a naive implementation of the Fibonacci sequence:

src
1def fibonacci_naive(number: int) -> int:
2    if number <= 1:
3        return number
4
5    return fibonacci_naive(number - 1) + fibonacci_naive(number - 2)

The execution time are:

n

t(s)

0

4.9e-07

1

3.2e-07

2

5.1e-07

3

5.9e-07

4

4.7e-07

5

5.8e-07

6

8.2e-07

7

1.1e-06

8

1.5e-06

9

2.2e-06

10

3.5e-06

11

5.6e-06

12

8.9e-06

13

1.4e-05

14

2.3e-05

15

3.7e-05

16

6.1e-05

17

9.6e-05

18

1.6e-04

19

2.5e-04

20

4.1e-04

21

6.7e-04

22

1.1e-03

23

1.8e-03

24

2.9e-03

25

4.7e-03

26

7.4e-03

27

1.2e-02

28

2.0e-02

29

3.3e-02

30

5.3e-02

31

8.5e-02

32

1.4e-01

33

2.2e-01

34

3.6e-01

35

5.8e-01

36

9.5e-01

37

1.5e+00

38

2.5e+00

39

4.1e+00

40

6.6e+00

41

1.1e+01

42

1.7e+01

Execution times rapidly become unacceptable for such a simple problem. The number of subproblems increases exponentially, so is the execution time. A solution has been presented in the functools section with the cache decorator:

src
1@cache
2def fibonacci(number: int) -> int:
3    if number <= 1:
4        return number
5
6    return fibonacci(number - 1) + fibonacci(number - 2)

n

t(s)

0

7.6e-07

1

5.5e-07

2

7.5e-07

3

7.0e-07

4

4.9e-07

5

4.7e-07

6

3.7e-07

7

3.5e-07

8

3.6e-07

9

3.2e-07

10

4.1e-07

11

3.5e-07

12

3.2e-07

13

3.1e-07

14

4.1e-07

15

4.3e-07

16

3.7e-07

17

3.4e-07

18

2.9e-07

19

3.2e-07

20

3.0e-07

21

6.3e-07

22

3.2e-07

23

3.3e-07

24

3.2e-07

25

3.4e-07

26

3.4e-07

27

3.2e-07

28

3.1e-07

29

3.2e-07

30

3.4e-07

31

3.4e-07

32

3.1e-07

33

3.4e-07

34

3.1e-07

35

3.1e-07

36

3.5e-07

37

3.3e-07

38

3.0e-07

39

2.9e-07

40

3.0e-07

41

3.0e-07

42

7.5e-07

Subproblem definition

Usually, the hard part lies in the subproblem definition. They can (and even must) overlap; they must form an optimal substructure; the number of input parameters must be minimal.

Exercise (intermediate)

The length of the longest common subsequence is a typical dynamic programming exercise. The goal is to find inside two strings, the length of the longest subsequence of potentially non adjacent common letters. Imagine that you want to quantify how similar two mutated DNA are.

  1. Express the subproblem, implement. The hints below will probably be needed.

  2. Understand and comment the code in the collapsable section below.

  3. Test.

  4. Complexity, with or without memoization.

Hint 1
src
 1def length_longest_common_sequence_empty_0(first: str, second: str) -> int:
 2    def llcs_nested(ind_first: int, ind_second: int) -> int:
 3        """from the end of the two strings up to ind_first and ind_second
 4        respectively for the first and second string,
 5        counts how many common letters they share.
 6
 7        "x x x x X x"
 8                 A--
 9                 |
10                ind_first
11        "y y Y y y y"
12             A------
13             |
14            ind_second
15
16        if the letters at ind_first and ind_second are equal, they count in the LLCS
17        otherwise, the LLCS does not change and one can either drop the letter from
18        the first or the second string, the best choice is the one which ultimately
19        leads to the "longest" LLCS."""
20        ...
21        return 0  #
22
23    return 0  #
Hint 2

The internal structure is given below.

src
 1def length_longest_common_sequence_empty_1(first: str, second: str) -> int:
 2    def llcs_nested(ind_first: int, ind_second: int) -> int:
 3        """from the end of the two strings up to ind_first and ind_second
 4        respectively for the first and second string,
 5        counts how many common letters they share.
 6
 7        "x x x x X x"
 8                 A--
 9                 |
10                ind_first
11        "y y Y y y y"
12             A------
13             |
14            ind_second
15
16        if the letters at ind_first and ind_second are equal, they count in the LLCS
17        otherwise, the LLCS does not change and one can either drop the letter from
18        the first or the second string, the best choice is the one which ultimately
19        leads to the "longest" LLCS."""
20        if ...:
21            return 0
22
23        if ...:
24            ...
25
26        return ...
27
28    return llcs_nested(len(first) - 1, len(second) - 1)
Correction of 1.
src
 1def length_longest_common_sequence_uncommented(first: str, second: str) -> int:
 2    def llcs_nested(ind_first: int, ind_second: int) -> int:
 3        """from the end of the two strings up to ind_first and ind_second
 4        respectively for the first and second string,
 5        counts how many common letters they share.
 6
 7        "x x x x X x"
 8                 A--
 9                 |
10                ind_first
11        "y y Y y y y"
12             A------
13             |
14            ind_second
15
16        if the letters at ind_first and ind_second are equal, they count in the LLCS
17        otherwise, the LLCS does not change and one can either drop the letter from
18        the first or the second string, the best choice is the one which ultimately
19        leads to the "longest" LLCS."""
20        if min(ind_first, ind_second) < 0:
21            return 0
22
23        if first[ind_first] == second[ind_second]:
24            return llcs_nested(ind_first - 1, ind_second - 1) + 1
25
26        return max(
27            llcs_nested(ind_first, ind_second - 1),
28            llcs_nested(ind_first - 1, ind_second),
29        )
30
31    return llcs_nested(len(first) - 1, len(second) - 1)
Correction
src
 1def length_longest_common_sequence(first: str, second: str) -> int:
 2    def llcs_nested(ind_first: int, ind_second: int) -> int:
 3        """from the end of the two strings up to ind_first and ind_second
 4        respectively for the first and second string,
 5        counts how many common letters they share.
 6
 7        "x x x x X x"
 8                 A--
 9                 |
10                ind_first
11        "y y Y y y y"
12             A------
13             |
14            ind_second
15
16        if the letters at ind_first and ind_second are equal, they count in the LLCS
17        otherwise, the LLCS does not change and one can either drop the letter from
18        the first or the second string, the best choice is the one which ultimately
19        leads to the "longest" LLCS."""
20        # if one of the two strings is empty, there is obviously no common letters
21        # with the other
22        if min(ind_first, ind_second) < 0:
23            return 0
24
25        # if the letters pointed in the two strings are equal
26        # they are part of the LCS, thus the LLCS is equal to
27        # 1 plus the LLCS of the remaining left part of the two
28        # strings
29        if first[ind_first] == second[ind_second]:
30            return llcs_nested(ind_first - 1, ind_second - 1) + 1
31
32        # it the letters are not equal, then either drop one letter
33        # of the first or the second. The correct choice is the
34        # one which leads to the maximum LLCS
35        return max(
36            llcs_nested(ind_first, ind_second - 1),
37            llcs_nested(ind_first - 1, ind_second),
38        )
39
40    # start from the very end
41    return llcs_nested(len(first) - 1, len(second) - 1)
tests
1def test_length_longest_common_sequence() -> None:
2    assert length_longest_common_sequence("abcdef", "bacedf") == 4
3    assert length_longest_common_sequence("abcdef", "fedc") == 1
4    assert length_longest_common_sequence("abcdef", "xyzz") == 0

  1. For the complexity, let us focus on the case without any common elements. It means that at every recursion, two recursions are called (one dropping the last element of the first sequence, the other dropping the last element of the second). Each call makes one comparison which is defined as the costly operation.

    It means that a tree is created, with a branching factor of 2 is created. If one starts with two sequences of length \(n\), the path where one drops systematically the last element of the first sequence has a depth of \(n\). The path where one drops alternatively from the first and the second sequence has a depth of \(2 n\). At each depth level, the total number of calls is doubled. The growth is exponential: \(2^{2n}\).

    Now, with memoization, the problem can be looked from an other perspective. The caching is performed on 2 integers: the current index of the first sequence, and the one of the second. It means that the cache contains at most \(n^2\) entries, and as a result the function has been executed at most \(n^2\) times.

Note

The function max (and min and sort) has a very useful optional argument: key=. This argument is a callable which used on the element prior to comparison.

For example max([-3, 2]) is 2,

but max([-3, 2], key=abs) is -3

It means that one can concisely select the longest sequence between several:

max([(2, 2), (4, 4, 4, 4), (3, 3, 3)], key=len) is (4, 4, 4, 4)

Exercise (difficult)

The longest non-decreasing subsequence is a classic dynamic programming problem. The goal is to find a sequence of potentially non adjacent element. The subsequence consists of increasing (or equal) elements inside another sequence. For example: in [3, 1, 4, 2, 1, 2 , 3], [1, 4] and [2, 2 , 3] are non-decreasing subsequences, however the longest is [1, 2, 2 , 3].

  1. Express the subproblem, implement. The hints below will probably be needed.

  2. Understand and comment the code in the collapsable section below.

  3. Test.

Hint 1

The hardest part of the exercise is to find what the subproblem is:

src
 1def longest_nondecreasing_subsequence_empty_0(seq: list[int]) -> list[int]:
 2    @cache
 3    def lnds_nested(current: int) -> list[int]:
 4        """find the LDNS from the start of seq and
 5        finishing at index current by element seq[current].
 6         0  1  2  3  4
 7        [x, x, X, x, x]
 8               A
 9         --->  |
10         ind  current
11
12        ldns_nested(2) is the LDNS between 0 and 2 which
13        ends with X (=seq[2])
14        """
15        ...
16
17    ...
18    return []  #
Hint 2

The internal structure is given below, the lines with ... or ended by # have to be completed:

src
 1def longest_nondecreasing_subsequence_empty_1(seq: list[int]) -> list[int]:
 2    @cache
 3    def lnds_nested(current: int) -> list[int]:
 4        """find the LDNS from the start of seq and
 5        finishing at index current by element seq[current].
 6         0  1  2  3  4
 7        [x, x, X, x, x]
 8               A
 9         --->  |
10         ind  current
11
12        ldns_nested(2) is the LDNS between 0 and 2 which
13        ends with X = (seq[2])
14        """
15        elt: int = seq[current]
16        longest_subseq_with_current = [elt]
17        for ind in range(current):
18            if ...:
19                longest_subseq_with_current = ...
20
21        return []  #
22
23    seq_max = ...
24    return []
Correction of 1.
src
 1def longest_nondecreasing_subsequence_uncommented(seq: list[int]) -> list[int]:
 2    @cache
 3    def lnds_nested(current: int) -> list[int]:
 4        """find the LDNS from the start of seq and
 5        finishing at index current by element seq[current].
 6         0  1  2  3  4
 7        [x, x, X, x, x]
 8               A
 9         --->  |
10         ind  current
11
12        ldns_nested(2) is the LDNS between 0 and 2 which
13        ends with X (=seq[2])
14        """
15        elt: int = seq[current]
16        longest_subseq_with_current = [elt]
17        for ind in range(current):
18            if seq[ind] <= elt:
19                longest_subseq_with_current: list[int] = max(
20                    longest_subseq_with_current,
21                    lnds_nested(ind) + [elt],
22                    key=len,
23                )
24        return longest_subseq_with_current
25
26    seq_max = max(
27        (lnds_nested(ind) for ind in range(len(seq))),
28        key=len,
29    )
30    return seq_max
Correction
src
 1def longest_nondecreasing_subsequence(seq: list[int]) -> list[int]:
 2    @cache
 3    def lnds_nested(current: int) -> list[int]:
 4        """find the LDNS from the start of seq and
 5        finishing at index current by element seq[current].
 6         0  1  2  3  4
 7        [x, x, X, x, x]
 8               A
 9         --->  |
10         ind  current
11
12        ldns_nested(2) is the LDNS between 0 and 2 which
13        ends with X (=seq[2])
14        """
15        elt: int = seq[current]
16        # smallest possible ldns with current is [elt] only
17        # will be updated below
18        # longest_subseq_with_current represents the best
19        # candidate for ldns_nested(current) so far
20        longest_subseq_with_current = [elt]
21        # - scanning every element at index ind on the left of current,
22        #   first determine if [elt] can extend lnds_nested(ind)
23        #   since ldns_nested[ind] ends with seq[ind]
24        #   [elt] can extend this subsequence only if seq[ind]<=elt
25        # - then, update ldns_nested(current) only if
26        #   the extension of lnds_nested(ind) by [elt]
27        #   is longer than ldns_nested(current) up to now.
28        for ind in range(current):
29            if seq[ind] <= elt:
30                longest_subseq_with_current: list[int] = max(
31                    longest_subseq_with_current,
32                    lnds_nested(ind) + [elt],
33                    key=len,
34                )
35        return longest_subseq_with_current
36
37    # the global ldns is the longest of the ldns_nested(ind)
38    # for every value of ind
39    seq_max = max(
40        (lnds_nested(ind) for ind in range(len(seq))),
41        key=len,
42    )
43    return seq_max
tests
1def test_longest_nondecreasing_subsequence() -> None:
2    expected = [1, 2, 2, 3]
3    assert longest_nondecreasing_subsequence([3, 1, 4, 2, 1, 2, 3]) == expected