UNIT -III Dynamic programming

Dynamic Programming (DP) is a problem-solving technique used in computer science to

efficiently solve complex problems by breaking them into smaller overlapping subproblems
and storing their results to avoid repeated computation.

 More general and powerful than divide and conquer

 Break up a problem into (in)(dependent) sub-problems
 Generally, there is a sequence of problems
 Identify the optimal substructure: when optimal solution to a problem is made up of
optimal solution to smaller subproblems
 Build up solution to larger and larger subproblems
 Identify redundancy and repetitions
 Use memoization or build up memo on the run

Dynamic Programming is often used in optimization problems (A problem with many

possible solutions for which we want to find an optimal solution)

Dynamic Programming works when a problem has the following two main properties.

 Overlapping Subproblems

 Optimal Substructure

Overlapping Subproblems:

 When a recursive algorithm would visit the same subproblems repeatedly, then a
problem has overlapping subproblems. Like Divide and Conquer, Dynamic
Programming combines solutions to sub-problems. Dynamic Programming is mainly
used when solutions of same subproblems are needed again and again.

Optimal Substructure:

 The Principle of Optimality To use dynamic programming the problem must observe
the principle of optimality, that whatever the initial state is, remaining decisions must
be optimal with regard the state following from the first decision.
When developing a dynamic-programming algorithm, we follow a sequence of four steps:

1. Characterize the structure of an optimal solution.

2. Recursively define the value of an optimal solution.

3. Compute the value of an optimal solution, typically in a bottom-up fashion.

4. Construct an optimal solution from computed information

Algorithm design technique

 A technique for solving problems that have

a. an optimal substructure property (recursion)
b. overlapping subproblems
 Idea: Do not repeatedly solve the same subproblems, but solve them only once and
store the solutions in a dynamic programming table

Example: Fibonacci numbers

• F(0) =0; F(1)=1; F(n)=F(n-1)+F(n-2) for n  2

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

Example:

Fibonacci numbers • F(0)=0; F(1)=1; F(n)=F(n-1)+F(n-2) for n  2

implement this recursion directly:

Dynamic-programming hallmark

 Overlapping subproblems A recursive solution contains a “small” number of distinct

subproblems repeated many times.
 The number of distinct Fibonacci subproblems is only n
 Dynamic-programming There are two variants of dynamic programming:
i. Bottom-up dynamic programming (often referred to as “dynamic
programming”)
ii. Memoization

Bottom-up dynamic programming algorithm

Store 1D DP-table and fill bottom-up

Memoization algorithm Memoization:

 Use recursive algorithm. After computing a solution to a subproblem, store it in a

table.
 Subsequent calls check the table to avoid redoing work

3.1 ROD CUTTING

The Rod Cutting Problem is a classic example of Dynamic Programming (DP) that
demonstrates how breaking a problem into smaller subproblems leads to an optimal solution.

The rod-cutting problem is the following.

 Given a rod of length n inches and a table of prices p i for i D 1; 2; : : : ; n, determine

the maximum revenue r n obtainable by cutting up the rod and selling the pieces.
 If the price p n for a rod of length n is large enough, an optimal solution might require
no cutting at all
 Fig: 3.1 A sample price table for rods. Each rod of length i inches earns
the company pi dollars of revenue.

Fig:3.2 The 8 possible ways of cutting up a rod of length 4.

 Above each piece is the value of that piece, according to the sample price chart of
Figure 3.2.
 The optimal strategy is part (c)4 cutting the rod into two pieces of length 24which has
total value 10.

Recurrence Relation

Let dp[n] be the maximum profit for length n.

dp [n]=max ⁡ ( price[i−1]+dp [n−i])

1 ≤ i≤ n

Recursive top-down implementation

It takes as input an array of prices and an integer n, and it returns the maximum

revenue possible for a rod of length n.

For length n D 0, no revenue is possible, and

so CUT-ROD returns 0 in line 2.

Line 3 initializes the maximum revenue q to , so that the for loop in lines 4-5 correctly
computes

Line 6 then returns this value.

A simple induction on n proves that this answer is equal to the desired answer r n , using
equation.
There are usually two equivalent ways to implement a dynamic-programming

approach.

Solutions to the rod-cutting problem illustrate both of them.

The first approach is top-down with memoization.

The second approach is the bottom-up method.

Top-down with memoization.

 The procedure now first checks to see whether it has previously solved this
subproblem.
 If so, it returns the saved value, saving further computation at this level.
 If not, the procedure computes the value in the usual manner but also saves it.
 We say that the recursive procedure has been memoized:
 it remembers what results it has computed previously.

Bottom-up method.

 This approach typically depends on some natural notion of the size of a

subproblem, such that solving any particular subproblem depends only on solving
smaller subproblems.
 Solve the subproblems in size order, smallest first, storing the solution to each
subproblem when it is first solved.
 In this way, when solving a particular subproblem, there are already saved
solutions for all of the smaller subproblems its solution depends upon.
 You need to solve each subproblem only once, and when you first see it, you have
already solved all of its prerequisite subproblems.
The main procedure MEMOIZED-CUT-ROD initializes a new auxiliary array with
the value which,
since known revenue values are always non negative is a convenient choice for denoting
“unknown.” MEMOIZED-CUT-ROD then calls its helper procedure, MEMOIZED-CUT-
ROD-AUX, which is just the memorized version of the exponential-time procedure, CUT-
ROD. It first checks in line 1 to see whether the desired value is already known and, if it is,
then line 2 returns it. Otherwise, lines 3-7 compute the desired value q in the usual manner,
line 8 saves it in and line 9 returns it.

 Line 1 of BOTTOM-UP-CUT-ROD creates a new array in which to save the

results of the subproblems,
  line 2 initializes r[0] to 0, since a rod of length 0 earns no revenue.
 Lines 3-6 solve each subproblem of size j , for j D 1; 2; : : : ; n, in order of increasing
size.
 The approach used to solve a problem of a particular size j is the same as that used by
CUT-ROD, except that line 6 now directly references array entry r[j-i] instead of
making a recursive call to solve the subproblem of size j - i .
 Line 7 saves in r[j] c the solution to the subproblem of size j .
 Finally, line 8 returns r[n], which equals the optimal value r n .

Time Complexity

 O(n²) → because for each length, we try all possible cuts

Space Complexity

 O(n)

MATRIX CHAIN MULTIPLICATION PROBLEM

 We can multiply two matrices A and B only if they are compatible: the number of
columns of A must equal the number of rows of B.
 If A is a p ×q matrix and B is a q ×r matrix, the resulting matrix C is a p ×r matrix.
 There are p.r total entries in C and each takes O(q) time to compute, thus the total
time to multiply these two matrices is dominated by the number of scalar
multiplication, which is p.q.r.
 The time to compute C is dominated by the number of scalar multiplications which is
p.q.r.
 We shall express costs of multiplying two matrices in terms of the number of scalar
multiplications.
 Matrix multiplication is an associative operation, but not a commutative operation.

 By this, we mean that we have to follow the above matrix order for multiplication, but
we are free to parenthesize the above multiplication depending upon our need.
 For example,

 To illustrate the different costs incurred by different parenthesizations of a matrix

product, consider the problem of a chain of three matrices.
 Suppose that the dimensions of the matrices are 10×100, 100×5, and 5 × 50,
respectively.
 The possible order of multiplication are:
 a) If we multiply according to the parenthesization ((A1 A2)A3) to compute the 10 ×
5 matrix product A1 A2, we perform 10 · 100 · 5 = 5000 scalar multiplications
To multiply this matrix product A1 A2 by matrix A3, we perform another 10 · 5 ·
50=2500scalar multiplications
Hence, to compute the product ((A1 A2)A3), a total of 7500 scalar multiplications.
  b) If instead we multiply according to the parenthesization (A1(A2 A3)), to compute
the 100*50 matrix product A2 A3 we perform 100 ·5 ·50 = 25,000 scalar
multiplications, to multiply this matrix product A2 A3 by matrix A1, we perform
another 10 · 100· 50=50,000scalar multiplications.
Hence, to compute the product (A1(A2 A3)), a total of 75,000 scalar multiplications.

 Thus, computing the product according to the first parenthesization is 10 times faster.
 The matrix-chain multiplication problem can be stated as follows: Given a sequence
of n matricesA1, A2, ... An, and their dimensions p0, p1, p2, ..., pn,
 where i = 1, 2, ..., n, matrix Ai has dimension pi1 × pi, determine the order of
multiplication that minimizes the number of scalar multiplications.
 Note that in the matrix-chain multiplication problem, we are not actually multiplying
matrices.
 Our goal is only to determine an order for multiplying matrices that has the lowest
cost

Step 1: The structure of an optimal parenthesization Our first step in the dynamic-
programming paradigm is to find the optimal substructure and then use it to construct an
optimal solution to the problem from optimal solutions to subproblems.

 For the matrix-chain multiplication problem, we can perform this step as follows:
 For convenience, let us adopt the notation Ai..j, where i ≤ j , for the matrix that
results from evaluating the product Ai Ai+1 · · · Aj .
 Observe that if the problem is nontrivial, i.e., i < j , then any parenthesization of the
product Ai Ai+1 · · · Aj must split the product between Ak and Ak+1 for some
integer k in the range i ≤ k < j .
 That is, for some value of k, we first compute the matrices Ai..k and Ak+1.. j and then
multiply them together to produce the final product Ai.. j .
 The cost of this parenthesization is thus the cost of computing the matrix Ai..k , plus
the cost of computing Ak+1.. j , plus the cost of multiplying them together.

Step 2: Recursively define the value of an optimal solution To help us keep track of solutions
to subproblems, we will use a table, and build the table in a bottom up manner.
For 1 ≤ i ≤ j ≤ n, let m[i, j] be the minimum number of scalar multiplications needed to
compute the Ai..j.

The optimum cost can be described by the following recursive formulation.

 To keep track of optimal sub solutions, we store the value of k in a table s[i, j].
 The place at which we split the product Ai..j to get an optimal parenthesization.
 That is, s[i, j] = k such that m[i, j] = m[i, k] + m[k + 1, j] + pi − 1 . pk . pj.

Step 3: Computing the value of an optimal costs we perform the third step of the dynamic-
programming paradigm and compute the optimal cost by using a tabular, bottom-up
approach.

 The following pseudo-code assumes that matrix Ai has dimensions pi−1×pi for i=1,
2, . . . , n. The input is a sequence p = p0, p1, . . . , pn, where length[p] = n + 1.
 The procedure uses an auxiliary table m[1 . . n, 1 . . n] for storing the m[i, j ] costs and
an auxiliary table s[1 . . n, 1 . . n] that records which index of k achieved the optimal
cost in computing m[i, j ].
 We will use the table s to construct an optimal solution

 Time Complexity of matrix chain multiplication is : O(n^3)

Step 4: Constructing an optimal solution The array s[i, j] can be used to extract the actual
sequence.

 The basic idea is to keepasplit markerin s[i, j] that indicates what is the best split. The
initial call PRINT-OPTIMAL-PARENS(s, 1, n) prints anoptimalparenthesization of
A1, A2, . . . , An

Elements of the Greedy Strategy – Greedy Algorithm

 A greedy algorithm obtains an optimal solution to a problem by making a sequence of

choices.
 At each decision point, the algorithm makes the choice that seems best at the moment.

properties of greedy methods.

1. Determine the optimal substructure of the problem.

2. Develop a recursive solution.
3. Show that if you make the greedy choice, then only one subproblem remains.
4. Prove that it is always safe to make the greedy choice. (Steps 3 and 4 can occur
5. in either order.)
6. Develop a recursive algorithm that implements the greedy strategy.
7. Convert the recursive algorithm to an iterative algorithm.
Design greedy algorithms according to the following sequence of steps:
1. Cast the optimization problem as one in which you make a choice and are left
with one subproblem to solve.
2. Prove that there is always an optimal solution to the original problem that makes
the greedy choice, so that the greedy choice is always safe.
3. Demonstrate optimal substructure by showing that, having made the greedy
choice, what remains is a subproblem with the property that if you combine an
optimal solution to the subproblem with the greedy choice you have made, you
arrive at an optimal solution to the original problem.
1. Greedy Choice Property
Definition: A globally optimal solution can be arrived at by making a locally optimal
(greedy) choice at each step.
Characteristics:
 At each decision point, the algorithm makes whatever choice seems best at that
moment
 The choice cannot depend on future choices or solutions to subproblems
 The choice is never reconsidered once made
Example: In the activity selection problem, always choosing the activity with the earliest
finish time is a greedy choice that leads to the optimal solution.
2. Optimal Substructure
Definition: A problem exhibits optimal substructure if an optimal solution to the problem
contains within it optimal solutions to subproblems.
Characteristics:
 The problem can be broken down into smaller subproblems
 The optimal solution to the overall problem depends on optimal solutions to its
subproblems
 Solutions to subproblems can be combined to solve the original problem
Example: In the activity selection problem, after selecting one activity, the remaining
problem is to select activities from those that don’t conflict with the chosen one.
3. Greedy Versus Dynamic Programming
While both greedy algorithms and dynamic programming exploit optimal substructure, they
differ in how they approach it:

Feature Greedy Algorithms Dynamic Programming

Choices Make one greedy choice and proceed Consider all possible choices

Subproblems Solve only one subproblem Solve multiple subproblems

Reuse No recomputation needed Stores solutions for reuse

Efficiency Typically, more efficient May be less efficient

Applicability Works when greedy choice property holds More widely applicable

When to Use Greedy Algorithms

Greedy algorithms are appropriate when:
1. The problem has optimal substructure
2. The greedy choice property holds
3. We need an efficient solution (often O(n log n) or better)
4. The problem can be solved by making a sequence of choices where each choice looks
best at the moment
Limitations of Greedy Algorithms
1. Not universally applicable: Many problems cannot be solved optimally with a
greedy approach
2. Local optima: May get stuck in locally optimal solutions that aren’t globally optimal
3. Difficult to prove correctness: Requires careful proof that the greedy choice leads to
global optimum
4. No backtracking: Cannot undo previous choices if they turn out to be suboptimal
Example: Proving the Activity Selection Algorithm
Let’s briefly apply these concepts to the activity selection problem:
1. Greedy Choice Property: Choosing the activity with earliest finish time leaves the
maximum remaining time for other activities
2. Optimal Substructure: After selecting one activity, the remaining problem is to
schedule activities that don’t conflict with it
3. Proof (Greedy Stays Ahead):
o Let S be an optimal solution with the first activity to finish being aⱼ
o If aⱼ ≠ a₁ (our greedy choice), we can replace aⱼ with a₁
o This creates another optimal solution S’ that includes our greedy choice
o Thus, the greedy choice is part of some optimal solution