1 of 38

Lecture 13

Dynamic programming

CSE 421 Autumn 2025

1

2 of 38

Previously…

2

3 of 38

Divide and conquer

  • Mergesort
  • Euclidean closest pair
  • Matrix and integer multiplication
  • Median/Selection finding

3

4 of 38

Today

4

  • The Dynamic Programming paradigm
  • Some examples (Tribonacci numbers, Edit Distance)

5 of 38

Dynamic Programming

5

6 of 38

The Dynamic Programming (DP) paradigm

6

  1. Break the problem into subproblems.
  2. Combine the answer to subproblems to get the answer to larger subproblems.

Dynamic programming is the natural evolution of Divide and Conquer

They share a common core:

Where they differ:

      • In Divide and Conquer, subproblems are independent.

7 of 38

The Dynamic Programming (DP) paradigm

7

  1. Break the problem into subproblems.
  2. Combine the answer to subproblems to get the answer to larger subproblems.

Dynamic programming is the natural evolution of Divide and Conquer

They share a common core:

Where they differ:

      • In Divide and Conquer, subproblems are independent. �In Dynamic Programming, the subproblems overlap, so we reuse answers to previous subproblems to be more efficient.

8 of 38

A first example: Tribonacci numbers

Input: Integer

Output: Tribonacci number defined recursively: and�.

8

There is a somewhat natural Divide and Conquer algorithm:

DCTribonacci():

  • If , output 1.
  • Else, output DCTribonacci(-) + DCTribonacci(-) + DCTribonacci(-)

9 of 38

A first example: Tribonacci numbers

Input: Integer

Output: Tribonacci number defined recursively: and�.

9

There is a somewhat natural Divide and Conquer algorithm:

DCTribonacci():

  • If , output 1.
  • Else, output DCTribonacci(-) + DCTribonacci(-) + DCTribonacci(-)

Runtime: ?

10 of 38

A first example: Tribonacci numbers

Easy to believe that runtime is exponential in by just looking at the number of nodes in the picture (each node is one call made by the algorithm)

11 of 38

A first example: Tribonacci numbers

To find the runtime formally, we need to solve:� and

Dropping the term (which makes the runtime even faster), we can “guess” the form of the solution to be for some . This is a solution iff:

(or )

There is a positive root:

So the runtime is approximately

Can we do better?

12 of 38

A first example: Tribonacci numbers

The key to a much faster runtime is to realize that the subproblems are greatly overlapping (they share the same subsubproblems, etc.). In the previous algorithm, we were solving the same problems over and over again.

13 of 38

Add “memoization” (and we get DP!)

13

Memo-Tribonacci(, Memo = {}):

  • If is in Memo, output Memo[].
  • If , output 1.
  • Memo[] = Memo-Tribonacci(-, Memo) + Memo-Tribonacci(-, Memo) + �Memo-Tribonacci(-, Memo)

It’s basically the same algorithm as before!

Except we’ve added “memo” table. We populate it as we go along, and we call previously stored results from it (instead of computing them again)

DCTribonacci():

  • If , output 1.
  • Else, output DCTribonacci(-) + DCTribonacci(-) + DCTribonacci(-)

14 of 38

Memo-Tribonacci runtime analysis

What is the largest could be?

14

15 of 38

Memo-Tribonacci runtime analysis

Theorem: .

Proof: By induction. Base cases are For induction��.

Corollary: Each can be expressed using bits.

15

16 of 38

Memo-Tribonacci runtime analysis

  • Computing each entry of the memo table takes how long?

16

17 of 38

Memo-Tribonacci runtime analysis

  • Computing each entry of the memo table takes 3 additions: time.
  • Total time:

17

18 of 38

Memo-Tribonacci runtime analysis

  • Computing each entry of the memo table takes 3 additions: time.
  • Total time:

18

19 of 38

Memo-Tribonacci runtime analysis

  • Computing each entry of the memo table takes 3 additions: time.
  • Total time: , total space:

19

20 of 38

Memo-Tribonacci runtime analysis

  • Computing each entry of the memo table takes 3 additions: time.
  • Total time: , total space: .

​

  • Could we have done better?
    • The time seems necessary.
    • Can we use less space?

20

21 of 38

Memo-Tribonacci runtime analysis

  • Computing each entry of the memo table takes 3 additions: time.
  • Total time: , total space: .

​

  • Could we have done better?
    • The time seems necessary.
    • Can we use less space? Yes! We don’t need to store the whole memo table: we can just store the three largest numbers computed so far. So, space .

21

22 of 38

Edit distance

  • Input: Two strings and
  • Output: A minimal sequence of edit operations converting into with allowed transformations being:�Delete, Insert (makes everything to the right move over by one), or Substitute (one character for another)

22

How many edits are needed here?

and may not have the same length

23 of 38

Edit distance

  • Input: Two strings and
  • Output: A minimal sequence of edit operations converting into with allowed transformations being:�Delete, Insert (makes everything to the right move over by one), or Substitute (one character for another)

23

How many edits are needed here?

and may not have the same length

24 of 38

Edit distance

  • Input: Two strings and
  • Output: A minimal sequence of edit operations converting into with allowed transformations being:�Delete, Insert (making everything to the right move over by one), or Substitute (one character for another)

24

How many edits are needed here?

and may not have the same length

25 of 38

A useful recursive definition of edit distance

25

Note that we can define/compute “edit distance” recursively!

Definitions:

    • Let be the prefix of the first characters of
    • Let be the prefix of the first characters of
    • Let be the minimal edit distance between and
    • Define (need to insert all characters)
    • Define (need to delete all characters)

Can we define in terms for or ?

26 of 38

A useful recursive definition of edit distance

26

If , what is ?

27 of 38

A useful recursive definition of edit distance

27

28 of 38

A useful recursive definition of edit distance

28

What if ?

29 of 38

A useful recursive definition of edit distance

29

30 of 38

A useful recursive definition of edit distance

30

Note: it doesn’t matter when gets substituted with . We still need to transform into .

31 of 38

A useful recursive definition of edit distance

31

32 of 38

A useful recursive definition of edit distance

32

33 of 38

A useful recursive definition of edit distance

33

34 of 38

A useful recursive definition of edit distance

Recursive definition :

    • If , then return
    • If , then return
    • If ,
      • Return
      • Else, return .

34

The edit distance of the original problem is

35 of 38

A useful recursive definition of edit distance

Recursive algorithm :

    • If , then return
    • If , then return
    • If ,
      • Return
      • Else, return .

35

The edit distance of the original problem is

This recursive algorithm is asking to solve the same problems many times over. ��It’s a perfect candidate for Dynamic Programming!

36 of 38

Memoization

36

Recall that the key feature of dynamic programming, other than recursion, is that we keep a “memo” table with results of subproblems we have solved

37 of 38

Memoization

37

Recall that the key feature of dynamic programming, other than recursion, is that we keep a “memo” table with results of subproblems we have solved

Note that the value only depends on:

  • The yellow square diagonal to it, if
  • The 3 yellow squares, if

DP algorithm overview: fill table column by column, left to right, bottom to top. �Output .

)asad

-

--

-

38 of 38

Edit distance DP algorithm

  • Initialize an all-zeros table .
  • Set
  • For to
    • For to
      • If , then set
      • Else, set .
  • Return .

38

DP-EditDistance:

time

iterations

time per loop

Total time: