DYNAMIC P ROGRAMMING

Dr. Sethukumarasamy K.

Assistant Professor
Department of Mathematics
School of Advanced Sciences

October 3, 2025

D R .S ETHUKUMARASAMY (VIT) DYNAMIC P ROGRAMMING O CTOBER 3, 2025 1 / 29

TABLE OF C ONTENTS

1 DYNAMIC P ROGRAMMING -I NTRODUCTION

2 T ERMINOLOGIES

3 B ELLMAN ’ S P RINCIPLE AND R ECURSION

4 A PPLICATIONS
Knapsack problem
Shortest-route problem
Resource Allocation Problem

5 R EFERENCES

D R .S ETHUKUMARASAMY (VIT) DYNAMIC P ROGRAMMING O CTOBER 3, 2025 2 / 29

 DYNAMIC P ROGRAMMING -I NTRODUCTION W HAT IS DP?

I NTRODUCTION

Definition

Dynamic Programming (DP) is a method for solving complex prob-

lems by breaking them down into simpler, overlapping subproblems.

Solves each subproblem only once and stores the result

(memoization/tabulation)
Builds up optimal solutions from smaller subproblems
Used for optimization problems with recursive structure

D R .S ETHUKUMARASAMY (VIT) DYNAMIC P ROGRAMMING O CTOBER 3, 2025 3 / 29

 DYNAMIC P ROGRAMMING -I NTRODUCTION W HY U SE DP?

W HY DP?

Saves Time: Avoids recomputing same subproblems (exponential →

polynomial time)
Efficient: Optimal use of memory by storing only necessary results
Guarantees Optimality: Finds globally optimal solution through
optimal substructure
Versatile: Applies to diverse problems (knapsack, shortest path,
sequence alignment)

D R .S ETHUKUMARASAMY (VIT) DYNAMIC P ROGRAMMING O CTOBER 3, 2025 4 / 29

 DYNAMIC P ROGRAMMING -I NTRODUCTION W HY U SE DP?

H ISTORY
Origins (1950s). Mathematician Richard E.
Bellman introduced “dynamic programming”
to formalize multi-stage decision making
under constraints.
Why the name. “Dynamic” because decisions
unfold over stages and each choice changes
future s
Core idea. Break a problem into subproblems
with the principle of optimality: an optimal
policy has optimal sub-policies from every
reachable state.
Impact. First applied to military/engineering
planning; now central in operations research,
control, economics, reinforcement learning,
Richard Ernest Bellman
and AI.
Image: Wikipedia

D R .S ETHUKUMARASAMY (VIT) DYNAMIC P ROGRAMMING O CTOBER 3, 2025 5 / 29

 T ERMINOLOGIES

T ERMINOLOGIES

Definition

A dynamic programming problem can be decomposed into a se-

quence of smaller sub-problems called stages. Each stage i repre-
sents a point where a decision is made.

Represents different time periods or decision points in the planning

horizon
At each stage, multiple decision alternatives are available
Examples: Each item in knapsack problem

D R .S ETHUKUMARASAMY (VIT) DYNAMIC P ROGRAMMING O CTOBER 3, 2025 6 / 29

 T ERMINOLOGIES

T ERMINOLOGIES

Definition

The state represents the condition of the decision process at a partic-

ular stage. State variables xi describe the status of the system.

Provides information for analyzing current decision’s future effects

Can be finite or infinite in number
Examples:
Specific city in shortest route problem
Remaining capacity in knapsack problem
Current equipment age in replacement problem

D R .S ETHUKUMARASAMY (VIT) DYNAMIC P ROGRAMMING O CTOBER 3, 2025 7 / 29

 T ERMINOLOGIES

T ERMINOLOGIES

Definition

A return function measures the worth or benefit of decisions made

at each stage, expressed as an algebraic equation fi (xi ).

Depends on both state variables and decisions made

Optimal policy yields maximum/minimum return for given state
Each decision affects the state at next stage
Helps arrive at optimal solution at current stage

D R .S ETHUKUMARASAMY (VIT) DYNAMIC P ROGRAMMING O CTOBER 3, 2025 8 / 29

 B ELLMAN ’ S P RINCIPLE AND R ECURSION

B ELLMAN ’ S P RINCIPLE

Bellman’s Principle of Optimality

The optimal policy must be one such that, regardless of how a par-
ticular state is reached, all later decisions (choices) proceeding from
that state must be optimal.

An optimal policy requires that whatever the initial state and initial
decision are, the remaining decisions must constitute an optimal
policy with regard to the state resulting from the first decision
Allows solving complex problems by breaking them into sequential
stages
Enables recursive optimization - solve one stage at a time

D R .S ETHUKUMARASAMY (VIT) DYNAMIC P ROGRAMMING O CTOBER 3, 2025 9 / 29

 B ELLMAN ’ S P RINCIPLE AND R ECURSION

F ORWARD AND B ACKWARD RECURSION

Backward Recursion:
Start from the last stage and work backward to the first
Determine optimal policy for each possible state at each stage
Commonly used in most DP problems
Forward Recursion:
Start from the first stage and proceed forward
Build optimal solution progressively through stages
Alternative approach for certain problem types

D R .S ETHUKUMARASAMY (VIT) DYNAMIC P ROGRAMMING O CTOBER 3, 2025 10 / 29

 B ELLMAN ’ S P RINCIPLE AND R ECURSION

W HY B ACKWARD R ECURSION P REFERRED ?

Guaranteed Relevance: Every computed state must lead to the final

optimal solution
Natural Pruning: Automatically ignores states that cannot reach the
goal
More Focused Computation: Evaluates only states that matter for the
final solution

D R .S ETHUKUMARASAMY (VIT) DYNAMIC P ROGRAMMING O CTOBER 3, 2025 11 / 29

 A PPLICATIONS K NAPSACK PROBLEM

K NAPSACK PROBLEM

The general bounded knapsack problem is of the form:

Maximize r1 m1 + r2 m2 + r3 m3 + · · · + rn mn
Subject to w1 m1 + w2 m2 + w3 m3 + · · · + wn mn ≤ W ,
0 ≤ m1 ≤ u1 , 0 ≤ m2 ≤ u2 , . . . , 0 ≤ mn ≤ un ,
m1 , m2 , . . . , mn ∈ Z.

Where
ri — benefit/value of item i;
wi — weight of item i;
mi — decision variable (copies of item i);
ui — maximum allowed copies of item i (stock limit);
W — knapsack capacity.

D R .S ETHUKUMARASAMY (VIT) DYNAMIC P ROGRAMMING O CTOBER 3, 2025 12 / 29

 A PPLICATIONS K NAPSACK PROBLEM

P ROBLEM

Suppose a 10-lb knapsack is to be filled with the items listed in the table.
Each item can be chosen at most once. To maximize total benefit, how
should the knapsack be filled? Use dynamic programming to solve this
problem.

Item Weight (lb) Benefit

1 4 11
2 3 7
3 5 12

D R .S ETHUKUMARASAMY (VIT) DYNAMIC P ROGRAMMING O CTOBER 3, 2025 13 / 29

 A PPLICATIONS K NAPSACK PROBLEM

S OLUTION
W = 10, w = (4, 3, 5), r = (11, 7, 12).

Maximize 11m1 + 7m2 + 12m3

Subject to 4m1 + 3m2 + 5m3 ≤ 10, m1 , m2 , m3 ∈ Z.

Stage 3. For capacity x3 ∈ {0, . . . , 10},

¹ º
10
w3 = 5 lb, r3 = 12 , ⇒ m3 = 0, 1, 2
5
Feasibility 5m3 ≤ x3
Return function f3 (x3 ) = max { 12 m3 : 5 m3 ≤ x3 }
m3 ∈{0,1,2}

D R .S ETHUKUMARASAMY (VIT) DYNAMIC P ROGRAMMING O CTOBER 3, 2025 14 / 29

 A PPLICATIONS K NAPSACK PROBLEM

S OLUTION

12 m3 Optimum solution

x3 m3 = 0 m3 = 1 m3 = 2 f3 (x3 ) m∗3

0 0 – – 0 0
1 0 – – 0 0
2 0 – – 0 0
3 0 – – 0 0
4 0 – – 0 0
5 0 12 – 12 1
6 0 12 – 12 1
7 0 12 – 12 1
8 0 12 – 12 1
9 0 12 – 12 1
10 0 12 24 24 2

D R .S ETHUKUMARASAMY (VIT) DYNAMIC P ROGRAMMING O CTOBER 3, 2025 15 / 29

 A PPLICATIONS K NAPSACK PROBLEM

S OLUTION

Stage 2. For capacity x2 ∈ {0, . . . , 10},

¹ º
10
w2 = 3 lb, r2 = 7, ⇒ m2 ∈ {0, 1, 2, 3}.
3
Feasibility: 3 m2 ≤ x2 .
Return function:
n ¡ ¢ o
f2 (x2 ) = max 7 m2 + f3 x2 − 3m2 : 3m2 ≤ x2 .
m2 ∈{0,1,2,3}

D R .S ETHUKUMARASAMY (VIT) DYNAMIC P ROGRAMMING O CTOBER 3, 2025 16 / 29

 A PPLICATIONS K NAPSACK PROBLEM

S OLUTION

7 m2 + f3 (x2 − 3m2 ) Optimum solution

x2 m2 = 0 m2 = 1 m2 = 2 m2 = 3 f2 (x2 ) m∗2

0 0 – – – 0 0
1 0 – – – 0 0
2 0 – – – 0 0
3 0 7 – – 7 1
4 0 7 – – 7 1
5 12 7 – – 12 0
6 12 7 14 – 14 2
7 12 7 14 – 14 2
8 12 19 14 – 19 1
9 12 19 14 21 21 3
10 24 19 14 21 24 0

D R .S ETHUKUMARASAMY (VIT) DYNAMIC P ROGRAMMING O CTOBER 3, 2025 17 / 29

 A PPLICATIONS K NAPSACK PROBLEM

S OLUTION

Stage 1. For capacity x1 ∈ {0, . . . , 10},

¹ º
10
w1 = 4 lb, r1 = 11, ⇒ m1 ∈ {0, 1, 2}.
4
Feasibility: 4 m1 ≤ x1 .
Return function:
n ¡ ¢ o
f1 (x1 ) = max 11 m1 + f2 x1 − 4m1 : 4m1 ≤ x1 .
m1 ∈{0,1,2}

D R .S ETHUKUMARASAMY (VIT) DYNAMIC P ROGRAMMING O CTOBER 3, 2025 18 / 29

 A PPLICATIONS K NAPSACK PROBLEM

S OLUTION

11 m1 + f2 (x1 − 4m1 ) Optimum solution

x1 m1 = 0 m1 = 1 m1 = 2 f1 (x1 ) m∗1

0 0 – – 0 0
1 0 – – 0 0
2 0 – – 0 0
3 7 – – 7 0
4 7 11 – 11 1
5 12 11 – 12 0
6 14 11 – 14 0
7 14 18 – 18 1
8 19 18 22 22 2
9 21 23 22 23 1
10 24 25 22 25 1

D R .S ETHUKUMARASAMY (VIT) DYNAMIC P ROGRAMMING O CTOBER 3, 2025 19 / 29

 A PPLICATIONS K NAPSACK PROBLEM

B ACKTRACKING & O PTIMAL S OLUTION

Capacity W = 10, w = (4, 3, 5), r = (11, 7, 12).
Stage 1 (pick m1 ):

f1 (10) = max { 11m1 + f2 (10 − 4m1 ) }

m1 ∈{0,1,2}

24 , 11 + f2 (6) = 11 + 14 = 25, |{z}

= max{ |{z} 22 } = 25.
| {z }
m1 =0 m1 =1 m1 =2

Thus m∗1 = 1 and remaining capacity x2 = 10 − 4 = 6.

Stage 2 (given x2 = 6, pick m2 ):

f2 (6) = max { 7m2 + f3 (6 − 3m2 ) }

m2 ∈{0,1,2,3}

= max{ |{z}
12 , |{z}
7 , |{z}
14 , infeasible } = 14.
m2 =0 m2 =1 m2 =2

Thus m∗2 = 2 and remaining capacity x3 = 6 − 2 · 3 = 0.

D R .S ETHUKUMARASAMY (VIT) DYNAMIC P ROGRAMMING O CTOBER 3, 2025 20 / 29
 A PPLICATIONS K NAPSACK PROBLEM

Stage 3 (given x3 = 0, pick m3 ):

f3 (0) = max { 12m3 : 5m3 ≤ 0 } = 0 ⇒ m∗3 = 0.

m3 ∈{0,1,2}

Optimal packing: (m∗1 , m∗2 , m∗3 ) = (1, 2, 0)

Total weight: 4 · 1 + 3 · 2 + 5 · 0 = 10 lb

Maximum return: 11 · 1 + 7 · 2 + 12 · 0 = 25.

Conclusion
With capacity W = 10 and bounds m1 ∈ {0, 1, 2}, m2 ∈ {0, 1, 2, 3}, m3 ∈ {0, 1, 2},
the DP backtracking yields the optimal plan (m∗1 , m∗2 , m∗3 ) = (1, 2, 0) with to-
tal weight 10 lb and maximum return 25.

D R .S ETHUKUMARASAMY (VIT) DYNAMIC P ROGRAMMING O CTOBER 3, 2025 21 / 29

 A PPLICATIONS S HORTEST- ROUTE PROBLEM

P ROBLEM
Suppose we want to select the shortest highway route between two cities. The
network given below shows the possible routes between the starting city at node 1
and the destination city at node 7. The routes may pass through intermediate
cities (nodes 2–6). Arc labels are travel costs. Determine (i) the shortest path from
node 1 to node 7, and (ii) the corresponding minimum total cost.

2 12

5
7
8 9
8
1 3 7
9 6
5
7 6

4 13

D R .S ETHUKUMARASAMY (VIT) DYNAMIC P ROGRAMMING O CTOBER 3, 2025 22 / 29

 A PPLICATIONS S HORTEST- ROUTE PROBLEM

B ACKWARD R ECURSIVE E QUATION

Conclusion

The backward recursive equation for this prbblem is

f4 (x4 = 7) = 0,
© ª
fi (xi ) = min d(xi−1 , xi ) + fi−1 (xi−1 ) , i = 1, 2, 3.
all feasible routes (xi−1 , xi )

The order of computations is f3 → f2 → f1 .

D R .S ETHUKUMARASAMY (VIT) DYNAMIC P ROGRAMMING O CTOBER 3, 2025 23 / 29

 A PPLICATIONS S HORTEST- ROUTE PROBLEM

S TAGE 3 AND S TAGE 2 C OMPUTATIONS

Stage 3. Node 7 (x4 = 7) is connected to nodes 5 and 6 (x3 = 5, 6) with one
route each.

d(x3 , x4 ) Optimum solution

x3 x4 = 7 f3 (x3 ) x4∗
5 9 9 7
6 6 6 7

Stage 2. Route (2, 6) does not exist. Using f3 (x3 ) from Stage 3:

d(x2 , x3 ) + f3 (x3 ) Optimum solution

x2 x3 = 5 x3 = 6 f2 (x2 ) x3∗
2 12 + 9 = 21 – 21 5
3 8 + 9 = 17 9 + 6 = 15 15 6
4 7 + 9 = 16 13 + 6 = 19 16 5

D R .S ETHUKUMARASAMY (VIT) DYNAMIC P ROGRAMMING O CTOBER 3, 2025 24 / 29

 A PPLICATIONS S HORTEST- ROUTE PROBLEM

S TAGE 1 C OMPUTATION AND F INAL R OUTE

The optimum solution of stage 2 reads as follows: for cities 2 and 4, the shortest
routes pass through city 5, and for city 3, the shortest route passes through city 6.
Stage 1. From node 1, we have three alternative routes: (1, 2), (1, 3), and (1, 4).
Using f2 (x2 ) from stage 2, we get

d(x1 , x2 ) + f2 (x2 ) Optimum solution

x1 x2 = 2 x2 = 3 x2 = 4 f1 (x1 ) x2∗
1 7 + 21 = 28 8 + 15 = 23 5 + 16 = 21 21 4

Conclusion

Stage 1 links city 1 to city 4. Next, stage 2 links city 4 to city 5. Finally, stage
3 connects city 5 to city 7. The optimum route is 1 → 4 → 5 → 7, and the
associated distance is 21 miles.

D R .S ETHUKUMARASAMY (VIT) DYNAMIC P ROGRAMMING O CTOBER 3, 2025 25 / 29

 A PPLICATIONS R ESOURCE A LLOCATION P ROBLEM

R ESOURCE A LLOCATION

Minimize y12 + y22 + y32

Subject to y1 + y2 + y3 ≥ 15,

Goal: Minimize Z = y12 + y22 + y32 subject to y1 , y2 , y3 ≥ 0 and the resource

requirement y1 + y2 + y3 ≥ 15.
Key observation (binding): Since y 2 is increasing for y ≥ 0, the inequality is
tight at optimum: the best solution satisfies y1 + y2 + y3 = 15. (Using more
than 15 only increases the cost.)
Stages / State / Decision:
Stage i ∈ {1, 2, 3}; state si = remaining requirement before choosing yi .
Initialize s3 = 15; choose yi ∈ [0, si ]; transition si−1 = si − yi ; terminal
s0 = 0.
Bellman recursion (continuous):
(
© 2
ª 0, s=0
fi (s) = min y + fi−1 (s − y) , f0 (s) =
0≤y≤s +∞, s ̸= 0.
D R .S ETHUKUMARASAMY (VIT) DYNAMIC P ROGRAMMING O CTOBER 3, 2025 26 / 29
 A PPLICATIONS R ESOURCE A LLOCATION P ROBLEM

S OLUTION SETUP AND RECURRENCE

The problem is a three–stage DP with states

s3 = y1 + y2 + y3 ≥ 15, s 2 = y 1 + y 2 = s3 − y 3 , s1 = y 1 = s2 − y 2 .

Functional (recurrence) relations:

f1 (s1 ) = min y12 = (s2 − y2 )2 ,

0≤y1 ≤s1

f2 (s2 ) = min { y22 + f1 (s2 − y2 ) },

0≤y2 ≤s2

f3 (s3 ) = min { y32 + f2 (s3 − y3 ) }.

0≤y3 ≤s3

Thus, for stage 2:

y22 + (s2 − y2 )2
© ª
f2 (s2 ) = min
0≤y2 ≤s2
¡ 1 ¢2 ¡ 1
¢2 1 2
= 2 s 2 + s2 − 2 s 2 = 2 s2 ,

because the function y22 + (s2 − y2 )2 attains its minimum at y2 = 21 s2 .

D R .S ETHUKUMARASAMY (VIT) DYNAMIC P ROGRAMMING O CTOBER 3, 2025 27 / 29
 A PPLICATIONS R ESOURCE A LLOCATION P ROBLEM

S TAGE 3 AND F INAL VALUES

Also,
f3 (s3 ) = min { y32 + f2 (s3 − y3 ) } = min y32 + 21 (s3 − y3 )2 .
© ª
0≤y3 ≤s3 0≤y3 ≤s3

Hence, for s3 = 15,

y32 + 12 (15 − y3 )2 .
© ª
f3 (15) = min
0≤y3 ≤15

Since the minimum of y32 + 21 (15 − y3 )2 occurs at y3 = 5, we obtain

f3 (15) = (5)2 + 21 (15 − 5)2 = 25 + 50 = 75.

Thus s3 = 15 and y3 = 5; s2 = s3 − y3 = 10 ⇒ y2 = 21 s2 = 5;
s1 = s2 − y2 = 5 ⇒ y1 = s1 = 5.

Conclusion

Hence, the optimal policy is y1 = 5, y2 = 5, y3 = 5 with f3 (15) = 75.

D R .S ETHUKUMARASAMY (VIT) DYNAMIC P ROGRAMMING O CTOBER 3, 2025 28 / 29

 R EFERENCES

R EFERENCES

Hamdy [Link], 2003, Operations Research - An introduction, Prentice Hall.

Wayne L. Winston 2004, Operations Research - Applications and Algorithms,
Thomson Brooks-Cole.

D R .S ETHUKUMARASAMY (VIT) DYNAMIC P ROGRAMMING O CTOBER 3, 2025 29 / 29