Lecture 14

Dynamic programming II

CSE 421 Autumn 2026

1

Some midterm logistics

2

Monday November 9, at 5.30pm in JHN 102 or 075 (depending on the last digit of your UW ID), or scheduled with DRS.

• ~50% very similar to problems/concepts you have already seen in HWs, section (including handouts), lectures. ~50% new problem(s).
• Will cover content up to Wednesday’s lecture (and including HW 5).
• No advice sheet.
• You may practice with last year’s midterm and the practice midterm.

Previously…

3

The Dynamic Programming (DP) paradigm

4

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.

The Dynamic Programming (DP) paradigm

5

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.

Today

6

• Wrap up Edit Distance
• The Knapsack problem

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)

7

and may not have the same length

A useful recursive definition of edit distance

8

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

A useful recursive definition of edit distance

Recursive definition :

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

9

The edit distance of the original problem is

Memoization

10

Note that the value only depends on:

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

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

)asad

-

--

-

Finding the set of edits

• The previous algorithm only computes the edit distance.
• How do we also compute the set of edits that need to be made?
• Recall that we computed based on a local minimization of previous subproblems (when , we set to be the min over 3 other entries of the memo table)
• Solution: Also keep track of which subproblem achieved the minimization
• In the table, create an “edge” that points from to the subproblem that solved the optimization

11

Finding the set of edits

12

Recall: if , then --

Being in one case tells us that the associated transformation is the optimal way to solve the problem!

If , then there are three ways in which relates to the previous subproblems

For example, being in case 3 means that the optimal way to get from to�is to insert at the end, and do the optimal edits to get from to

Finding the set of edits

13

-

--

-

Finding the set of edits

14

-

--

-

. . .

Finding the set of edits

15

-

--

-

Finding the set of edits

16

The path from the top right corner to the bottom left tells us all the optimal edits.

Keeping track of all the edges just introduces an factor overhead in time and space.

Takeaways

• Identify the recursive structure of the problem you are trying to solve
• Iterate through subproblems starting from the “smallest” and building up to the “largest”. For each one:
• Find the optimal value (and record it), using the previously-computed optimal values to smaller subproblems.
• If useful, also record the choices made to obtain each optimal value. (If many smaller subproblems were considered as candidates, record which one was chosen.)
• Runtime given by: (size of the memo table) x (time it takes to solve each subproblem given the previous)

17

The Knapsack problem

18

Maximize the value of the items grabbed subject to the weight constraint of the bag

(We encountered a similar problem about �beans in HW 2: what’s the difference here?)

The Knapsack problem

Input: Items with positive integer weights and values ,�and a max weight for the bag.

Output: Subset such that and maximizes .

19

Let =

The Knapsack problem

Input: Items with positive integer weights and values ,�and a max weight for the bag.

Output: Subset such that and maximizes .

20

Brute-force algorithm: check all possible subsets , and choose the optimal one amongst those satisfying the weight constraint.

Runtime:

Let =

The Knapsack problem

Input: Items with positive integer weights and values ,�and a max weight for the bag.

Output: Subset such that and maximizes .

21

Brute-force algorithm: check all possible subsets , and choose the optimal one amongst those satisfying the weight constraint.

Runtime:

complexity of adding numbers and �(for each we have to do such additions to compute the value, and check the constraint)

Let =

A dynamic programming algorithm

22

For a DP algorithm, we need to find a recursive structure.

Can we find a recursive definition for the optimal value?

Concretely, we need to specify a function(s) (what does it take as input and what does it output?), that allows us to define the optimal value in terms of “optimal values” for smaller problems.

The functions:

• : takes as input and , and returns the optimal value attainable using items with total weight at most

• : takes as input and , and returns the subset attaining .

A dynamic programming algorithm

23

The functions:

• : takes as input and , and returns the optimal value attainable using items with total weight at most

• : takes as input and , and returns the subset attaining .

Base cases:

How can we express in terms of Val() at smaller inputs?

A dynamic programming algorithm

24

Observation: item is either in the optimal subset or not.

• If it is, then the best we can do is:

(best we can do with subject to weight constraint )

• If it’s not, then the best we can do is:

(best we can do with subject to weight constraint )

So,

A dynamic programming algorithm

25

So,

Correspondingly, depending on the maximization above, either or .

A dynamic programming algorithm

26

So,

By the way, why not consider a different function where , �which outputs the best value attainable with weight using elements from ?

The latter would later give a memo table later of size instead of !

Memoization for Knapsack

27

Table of

Memoization for Knapsack

28

Table of

Memoization for Knapsack

29

Path from top right corner to the bottom row tells you which items to include.

Table of

Knapsack DP algorithm

Filling the memo table:

• Let be sized tables and set .
• For from to , from to
• If
• Set and set
• Else, set and set

30

Returning output: Return as the max value. Walk from in to find which items to include.

Knapsack DP algorithm

Runtime

• Tables are of size and computing each entry takes time given past entries.
• Total compute time of tables is .
• To find the set , path walks from to each step. The path has length.
• Computing takes time .
• Total computation time: .

31

Knapsack DP algorithm

• The input for Knapsack is usually written in binary with each item weight expressed with bits and value with bits.
• Total input length is
• Runtime of Knapsack brute-force alg is , which is exponential in the input length
• Runtime of Knapsack DP is . Also exponential in the input length (though usually this is a much better runtime when weights are not too large)
• This is expected. The decision version of Knapsack is an -complete problem! We do not expect an efficient (polynomial-time) algorithm for Knapsack.

32

Runtime