Unit II- Dynamic programming and Linear Programming –

Dynamic Programming is a method to solve optimization problems by breaking them into

overlapping subproblems, solving each subproblem once, and storing their solutions.

Dynamic Programming (DP) is based on two fundamental elements:

1. Optimal Substructure

 A problem has an optimal substructure if the optimal solution to the problem can be
constructed from the optimal solutions of its subproblems.
 Example: In Shortest Path Problem, the shortest path from A → C via B is the
combination of:
o Shortest path from A → B and
o Shortest path from B → C.

2. Overlapping Subproblems

 A problem has overlapping subproblems if the same smaller problems are solved
multiple times.
 Instead of solving them again, we store their results (memoization/tabulation).
 Example: Fibonacci numbers →
o To compute F(5), we compute F(4) and F(3);
o but F(3) is recomputed multiple times in recursion → DP saves effort.

3. Subproblem Reuse (Memoization/Tabulation)

 DP works by storing solutions of already solved subproblems in a table (array,

map, etc.).
 Two approaches:
1. Top-Down (Memoization): Solve recursively, store results in a cache.
2. Bottom-Up (Tabulation): Solve smaller subproblems iteratively, build the
solution up.
🔹 Characteristics of DP

1. Characterize structure of the optimal solution (mathematical model).

2. Recursively define value of optimal solution (recurrence relation).
3. Use bottom-up approach to compute values of subproblems.
4. Construct the final solution using computed values.

🔹 Elements of Dynamic Programming

1. Optimal Substructure
o For a problem to be solved by DP, its optimal solution must be built from
optimal solutions of subproblems.
o Example: Shortest path problem.
2. Overlapping Subproblems
o The problem generates repeated subproblems.
o Instead of recomputing, DP stores their results in a table
(memoization/tabulation).
o Example: Fibonacci, Binomial Coefficients.
3. Subproblem Reuse
o Each distinct subproblem is solved once and reused.
o This reduces exponential complexity to polynomial.

🔹 Principle of Optimality

 Defined by Richard Bellman:

“In an optimal sequence of decisions, every subsequence must also be optimal.”
 If a problem does not satisfy this property, DP cannot be applied.
 Example:
o ✅ Shortest Path → satisfies principle of optimality.
o ❌ Longest Path → does not satisfy.

🔹 Applications of DP

 Make Change Problem

 0/1 Knapsack
 Optimal Binary Search Tree
 Travelling Salesman Problem (TSP)
 All Pairs Shortest Path (Floyd-Warshall)
 Assembly Line Scheduling
 Multistage Graph Problem

Elements of Dynamic Programming

123

Dynamic Programming (DP) is a powerful optimization technique used in mathematics and

computer science to solve complex problems by breaking them down into simpler subproblems.
By solving each subproblem only once and storing the results, DP avoids redundant
computations, leading to more efficient solutions.

Key Principles of Dynamic Programming

1. Optimal Substructure

Optimal substructure means that the optimal solution to a problem can be constructed from the
optimal solutions of its subproblems. For example, in the shortest path problem, the shortest path
from a source to a destination can be constructed by combining the shortest paths from the
source to intermediate nodes and from intermediate nodes to the destination.

2. Overlapping Subproblems

Overlapping subproblems occur when the same subproblems are solved multiple times in
different parts of the problem. For instance, in the Fibonacci sequence, the subproblem of
computing the Fibonacci number at index ( n-1 ) is used twice in the solution to the larger
problem of computing the Fibonacci number at index ( n ).

Approaches to Dynamic Programming

1. Top-Down Approach (Memoization)

In the top-down approach, also known as memoization, the problem is broken down into smaller
subproblems recursively. The results of solved subproblems are stored in a memoization table to
avoid redundant calculations. This approach is suitable when the number of subproblems is large
and many of them are reused2.

2. Bottom-Up Approach (Tabulation)

In the bottom-up approach, also known as tabulation, the smallest subproblems are solved first,
and their solutions are used to build up the solution to the main problem. This approach is
suitable when the number of subproblems is small and the optimal solution can be directly
computed from the solutions to smaller subproblems.

Binomial Coefficient using Dynamic Programming

The binomial coefficient (nk)\binom{n}{k}(kn​) represents the number of ways to choose kkk
items from nnn.

Recurrence Relation (Optimal Substructure):

C(n,k)= C(n−1,k−1)+C(n−1,k)

with base cases:

C(n,0)=C(n,n)=1
Dynamic Programming Approach

 Build values in a bottom-up table (Pascal’s triangle).

 Avoids recomputation of overlapping subproblems.

Algorithm (Tabulation):

1. Initialize C[i][0] = C[i][i] = 1

2. For other values: C[i][j] = C[i-1][j-1] + C[i-1][j]
3. Final answer = C[n][k]

Example:

For n=5,k=2

n\k 0 1 2

0 1

1 1 1

2 1 2 1

3 1 3 3

4 1 4 6

5 1 5 10

Complexity:

 Time: O(n⋅k)
 Space: O(n⋅k) (can be optimized to O(k)

📘 Matrix Chain Multiplication (MCM)

🔹 Definition

Matrix Chain Multiplication (or Matrix Chain Ordering Problem) is an optimization

problem that determines the most efficient way to multiply a sequence of matrices.

 The result of multiplication is the same regardless of how the matrices are
parenthesized (associativity),
 But the order of multiplication changes the number of scalar operations required.

🔹 Example

Let matrices be:

 A: 10 × 30
  B: 30 × 5
 C: 5 × 60

Two ways:

1. (AB)C → Cost = (10×30×5) + (10×5×60) = 1500 + 3000 = 4500

2. A(BC) → Cost = (30×5×60) + (10×30×60) = 9000 + 18000 = 27000

✅ Clearly, the first order is better.

🔹 Problem Complexity

 Number of possible parenthesizations = Catalan Number C(n-1)

C(n−1)=1n(2n−2n−1)C(n-1) = \frac{1}{n}\binom{2n-2}{n-1}C(n−1)=n1​(n−12n−2​)

 This grows exponentially → brute force is impractical.

🔹 Dynamic Programming Approach

We avoid recomputation of subproblems using DP.

Recurrence Formula
m[i,j]=i≤k<j i<k<jmin (​ m[i,k]+m[k+1,j]+p[i−1]⋅p[k]⋅p[j])

Where:

 m[i,j] = minimum number of multiplications to compute Ai...AjA_i ... A_jAi​...Aj​

 p[] = array of dimensions
 s[i,j] = index of split giving optimal solution (for parenthesization recovery)

🔹 Time & Space Complexity

 Time Complexity: O(n3)

 Space Complexity: O(n2)
 Longest Common Subsequence -
The Longest Common Subsequence of two sequences (say X and Y) is the longest
sequence that appears in both X and Y in the same relative order, but not necessarily
contiguously.

Given two strings text1 and text2, return the length of their longest common
subsequence. If there is no common subsequence, return 0.

A subsequence of a string is a new string generated from the original string with
some characters (can be none) deleted without changing the relative order of the
remaining characters.

 For example, "ace" is a subsequence of "abcde".

A common subsequence of two strings is a subsequence that is common to both

strings.

Example 1:

Input: text1 = "abcde", text2 = "ace"

Output: 3
Explanation: The longest common subsequence is "ace" and its length is 3.

Example 2:

Input: text1 = "abc", text2 = "abc"

Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.

Example 3:

Input: text1 = "abc", text2 = "def"

Output: 0
Explanation: There is no such common subsequence, so the result is 0.

Constraints:

 1 <= [Link], [Link] <= 1000

 text1 and text2 consist of only lowercase English characters.

🔹 Applications

 Bioinformatics (DNA/protein sequence alignment)

 File comparison (e.g., diff in Unix)
 Spell checking & plagiarism detection
 Data compression
📘 Linear Programming (LP)

🔹 Definition

Linear Programming (LP) is a mathematical optimization technique used to find the best
possible solution (maximum profit or minimum cost) for a linear objective function, subject
to a set of linear constraints (equalities or inequalities).

It is widely used in Operations Research, Business, Engineering, and Economics.

🔹 Components of Linear Programming

1. Decision Variables → The unknowns to determine (e.g., number of products to

produce).
2. Objective Function → Linear function to maximize/minimize (e.g., profit or cost).

Z=c1x1+c2x2+⋯+cnxnZ = c_1x_1 + c_2x_2 + \dots + c_nx_nZ=c1​x1​+c2​x2​+⋯+cn​xn​

3. Constraints → Linear equations/inequalities that restrict values of decision variables.

a11x1+a12x2+⋯+a1nxn≤b1a_{11}x_1 + a_{12}x_2 + \dots + a_{1n}x_n \leq

b_1a11​x1​+a12​x2​+⋯+a1n​xn​≤b1​

4. Non-Negativity Restrictions → xi≥0x_i \geq 0xi​≥0, since negative production/cost is

unrealistic.

🔹 General Formulation of LPP

Maximize/MinimizeZ=c1​x1​+c2​x2​+⋯+cn​xn​

Subject to:

a11x1+a12x2+⋯+a1nXn≤b1
a21x1+a22x2+⋯+a2nxn≤b2

x1,x2,…,xn≥0

🔹 Types of LPP

1. Manufacturing Problems → Decide units of products to maximize profit under

labor & resource constraints.
2. Diet Problems → Minimize cost of diet while meeting nutrition requirements.
3. Transportation Problems → Find cheapest way of transporting goods.

🔹 Methods to Solve LPP

1. Graphical Method (for 2 variables)

o Plot inequalities as lines on XY plane.
o Feasible region = intersection area of all constraints.
o Evaluate objective function at corner points.
o Optimal value is at one of the corners.
2. Simplex Method (for >2 variables)
o Systematic tabular approach.
o Iteratively improves solution until optimal is found.

🔹 Example (Graphical Method)

Maximize Z=6x+9yZ = 6x + 9yZ=6x+9y

Subject to:

 2x+3y≤122x + 3y \leq 122x+3y≤12

 x+y≤5x + y \leq 5x+y≤5
 x,y≥0x, y \geq 0x,y≥0

Feasible region corner points: (0,0), (0,4), (3,2), (5,0).

Evaluating Z:

 (0,0) → Z=0
 (0,4) → Z=36
 (3,2) → Z=36
 (5,0) → Z=30

✅ Max Z = 36 at (0,4) and (3,2).

✅ Min Z = 0 at (0,0).

🔹 Applications of Linear Programming

 Manufacturing → production scheduling, cost minimization.

 Transportation → finding cheapest delivery routes.
 Finance → portfolio optimization.
 Agriculture → crop planning.
  Energy → power generation & resource allocation.

Simplex Method
The Simplex Method is the most widely used algorithm to solve Linear Programming
Problems (LPPs) when there are more than two variables (because the graphical method
works only for 2 variables).

It is an iterative method that starts with an initial feasible solution and moves toward the
optimal solution by improving the objective function at each step.

Steps of the Simplex Method

1. Formulate the LPP

o Define decision variables.
o Write the objective function (Maximize or Minimize).
o Write the constraints (inequalities).
2. Convert inequalities into equations
o Add slack variables for ≤ constraints.
o Add surplus variables and artificial variables for ≥ or = constraints.
3. Construct the initial simplex tableau
o Represent the system in a tabular form with variables, constraints, and the
objective function.
4. Identify entering variable (pivot column)
o For maximization: choose the variable with the most negative coefficient in
the objective row.
5. Identify leaving variable (pivot row)
o Divide the RHS column by the pivot column values (positive only).
o The smallest ratio determines the leaving variable.
6. Perform pivot operation
o Make the pivot element = 1.
 o Make all other elements in pivot column = 0 (using row operations).
7. Repeat steps 4–6 until:
o All coefficients in the objective row are non-negative (for maximization).
o Or non-positive (for minimization).
8. Read the solution
o The final tableau gives the values of decision variables and the optimum value
of the objective function.

✅ Example (Maximization)
Maximize Z = 3x₁ + 2x₂
Subject to:

 2x₁ + x₂ ≤ 18
 2x₁ + 3x₂ ≤ 42
 3x₁ + x₂ ≤ 24
 x₁, x₂ ≥ 0

Duality Theory – Linear Programming

1. Concept of Duality

 Every Linear Programming Problem (Primal Problem) has another associated

problem called the Dual Problem.
 Both problems are mathematically related.
 Optimal value of primal = Optimal value of dual (if feasible solutions exist).
 Duality helps in economic interpretation, sensitivity analysis, and solving complex
problems.
2. Relationship between Primal and Dual

 Primal (Maximization problem with ≤ constraints) → Dual (Minimization with ≥

constraints).
 Primal (Minimization with ≥ constraints) → Dual (Maximization with ≤
constraints).

3. General Formulation

Primal (Maximization form):

Maximize Z=c1​x1​+c2​x2​+⋯+cn​xn​

Subject to:

A11x1 +a12x2+…a1nxn<b1

A21x1+ a22x2+…..a2nxn<b2

Am1x1+am2x2+..amnxn>0

Dual (Minimization form):

Minimize W = b1y1+b2y2+…bmym
Subject to:

A11y1+a21y2+///am1ym>c1

A12y1+ a22y2+..+am2ym> c2

a1n​y1​+a2n​y2​+⋯+amn​ym​≥cn​

y1​,y2​,…,ym​≥0

4. Rules for Conversion

 Number of constraints in primal = number of variables in dual.

 Number of variables in primal = number of constraints in dual.
 If primal has ≤ constraints → dual has ≥ constraints.
 If primal has ≥ constraints → dual has ≤ constraints.
 If primal is Maximization → dual is Minimization, and vice versa.

5. Properties of Duality

1. Dual of the dual = Primal.

2. If primal has an optimal finite solution, dual also has an optimal finite solution,
with equal objective values.
 Zmax=Wmin

3. If primal is unbounded, dual is infeasible (and vice versa).

4. Both primal and dual cannot be infeasible simultaneously.

6. Example

Primal:
Maximize Z = 5x₁ + 4x₂
Subject to:

 6x₁ + 4x₂ ≤ 24
 x₁ + 2x₂ ≤ 6
 –x₁ + x₂ ≤ 1
 x₁, x₂ ≥ 0

Dual:
Minimize W = 24y₁ + 6y₂ + 1y₃
Subject to:

 6y₁ + y₂ – y₃ ≥ 5
 4y₁ + 2y₂ + y₃ ≥ 4
 y₁, y₂, y₃ ≥ 0

7. Importance of Duality

 Provides economic interpretation of resources and constraints.

 Used in sensitivity analysis (effect of changes in constraints).
 Sometimes the dual problem is easier to solve than the primal.
 Widely applied in operations research, economics, transportation, and production
planning.