DYNAMIC
PROGRAMMING :
CONCEPTS
Design and Analysis of Algorithms
Date Presented By:
09/06/2025 Alvin C. Catalon
Course Objectives
Understand the principles of Dynamic
Programming.
Differentiate Dynamic Programming
from Divide-and-Conquer.
Formulate DP solutions using
recurrence relations and memoization.
Apply DP techniques in solving
problems like Fibonacci, Knapsack, and
Shortest Path.
What is Dynamic Programming?
Dynamic Programming is an algorithmic technique used for solving
complex problems by breaking them down into overlapping subproblems
and solving each subproblem only once, storing the result for future use.
Theory:
Invented by Richard Bellman (1950s)
Relies on Optimal Substructure and Overlapping Subproblems
Difference: DP vs Divide-and-Conquer
Feature Divide-and-Conquer Dynamic
Programming
Subproblem Overlap Usually disjoint Overlapping
Re-computation Repeated Avoided (memoized)
Storage None Uses tables/arrays
Principles of
Dynamic
Programming Optimal Substructure – A solution can be
constructed from solutions of its subproblems.
Overlapping Subproblems – The same
subproblems are solved multiple times.
Memoization or Tabulation – Store subproblem
solutions for reuse.
Example 1: Fibonacci
Sequence
Problem: Find the nth Fibonacci number.
Naive Recursive Approach (inefficient):
int fib(int n) {
if (n <= 1) return n;
return fib(n-1) + fib(n-2);
}
DP with Memoization (efficient):
int fibDP(int n, int[] memo) {
if (n <= 1) return n;
if (memo[n] != -1) return
memo[n];
memo[n] = fibDP(n-1,
memo) + fibDP(n-2, memo);
return memo[n];
}
Step-by-Step: Fibonacci with Tabulation
int fibTab(int n) {
Create a table dp[].
int[] dp = new int[n+1];
Initialize base cases: dp[0]=0,
dp[0] = 0;
dp[1]=1.
dp[1] = 1;
Fill in values iteratively.
for (int i = 2; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
Example 2: Knapsack
Problem
Problem Statement: Example 2 Solution (Knapsack Code):
Given weights and values of items, determine the maximum value achievable with a weight limit. int knapSack(int W, int wt[], int val[], int n) {
int dp[][] = new int[n+1][W+1];
Recurrence Relation: for (int i = 0; i <= n; i++) {
dp[i][w] = max(dp[i-1][w], value[i] + dp[i-1][w-weight[i]]) for (int w = 0; w <= W; w++) {
if (i==0 || w==0) dp[i][w] = 0;
else if (wt[i-1] <= w)
dp[i][w] = Math.max(val[i-1] + dp[i-1][w-
wt[i-1]], dp[i-1][w]);
else
dp[i][w] = dp[i-1][w];
}
}
return dp[n][W];
}
Example 3: Shortest
Path (Floyd-Warshall)
1 Problem: Find shortest distances between all pairs of
vertices.
Recurrence Relation:
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
2 loyd-Warshall Code
void floydWarshall(int graph[][], int V) {
int dist[][] = new int[V][V];
for (int i=0; i<V; i++)
for (int j=0; j<V; j++)
dist[i][j] = graph[i][j];
for (int k=0; k<V; k++)
for (int i=0; i<V; i++)
for (int j=0; j<V; j++)
dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
}
THANK YOU
FOR YOUR ATTENTION
AND PARTICIPATION
