Dynamic Programming

Presented By:
 Abduljabar Mohammed Madey
 Charles Kibet Ng’etich
 Dennis Onyinkwa Nyabaro
 Diero Ajwang
 Edwin Seno
 George Kihara Mburu
 Jeremiah Warui Wamwea
 John Kimani Muragu
 Joyadams Munene
 Marion Jeptoo
 Muriithi Alex Karani
 Nyairo Charles Magati
Introduction to Dynamic
Programming (DP)

 Dynamic programming is a method used to solve problems by

breaking them down into smaller, overlapping subproblems.

 Each subproblem is solved only once and stored for future use,
avoiding repeated calculations and improving efficiency.

 Core Concept: Instead of recalculating the same values

repeatedly, we remember previously computed results and reuse
them when needed.
 The problem can be broken into
overlapping subproblems
When to Use
Dynamic The problem exhibits optimal
substructure (optimal solution
Programmin contains optimal solutions to
subproblems)
g:
A brute-force recursive solution would
involve redundant calculations
Key Principles of Dynamic
Programming

 Optimal Substructure
A problem has optimal substructure if an optimal solution can be
constructed from optimal solutions of its subproblems.

For example, the shortest path from A to C through B consists of the

shortest path from A to B plus the shortest path from B to C.
Key Principles of Dynamic
Programming(cont)

 Overlapping Subproblems
Unlike divide-and-conquer algorithms (which solve independent
subproblems), DP solves problems in which the same subproblems
are solved multiple times.
Example: Fibonacci Sequence
Formula: F(n) = F(n-1) + F(n-2)
Without optimization, computing F(5) leads to recalculating values
like F(3) and F(2) multiple times.
The process of DP works in three phases:

1 2 3
Break Down: We split a Solve and Store: We solve Reuse Solutions: When
big, complicated problem each smaller problem, and we encounter the same
into smaller, simpler the answer is saved. This smaller problem again, we
problems that are easier to saved answer is like a don’t have to solve it from
solve. completed puzzle section. scratch. We can reuse the
answer we saved earlier.
 There are two main
approaches to
implementing DP:

DP Top-Down (Memoization)-
A recursive approach where
Approache we cache the results of
function calls to avoid
redundant computations.
s Overview
Bottom-Up (Tabulation) -
Tabulation builds up solutions
iteratively from the base
cases.
Memoization
Implementation
Approach
FIBONACCI SERIES
Pseudocode
FUNCTION Fibonacci_memoized (n, memo={})
IF n <=1:
RETURN n;
IF n NOT IN memo:
memo[n] = Fibonacci_memorized(n-1,memo) + Fibonacci_memorized(n-1,memo);
RETURN memo[n]

Explanation:
· This function uses caching (memo) to store previously computed Fibonacci numbers. This prevents recalculating subproblems
multiple times.
Flowchart
Start

n=5
memo = {}

n <=1? Yes Return n

No

n NOT
IN No
memo?

Yes

memo[n] = fib_mem(n-1, memo) + fib_

Return memo[n]
(n-2, memo)

END
Trace for n=5 Fibonacci number
Calls Recursion stack Comment
Call: fib(5) memo = {} [ fib(5) ]
fib(5) needs fib(4) + fib(3) → push fib(4) first. [ fib(4) fib(5) ]
fib(4) → needs fib(3) + fib(2) → push fib(3) [ fib(3) fib(4) fib(5) ]
fib(3) → needs fib(2) + fib(1) → push fib(2) [ fib(2) fib(3) fib(4) fib(5) ]
fib(2) → needs fib(1) + fib(0) → push fib(1) [ fib(1) fib(2) fib(3) fib(4) fib(5) ] Fib(1) returns 1 (base case) and is then popped off the
stack
Push fib(0) (second base case for fib(2)) [ fib(0) fib(2) fib(3) fib(4) fib(5) ] Fib(0) returns 0 (base case) and is then popped off the
stack
[ fib(0) fib(2) fib(3) fib(4) fib(5) ]
Calls Stack contraction & memo growth Comment
[ fib(2) fib(3) fib(4) fib(5) ]
Compute fib(2) = 1 + 0 = 1; Pop fib(2). [ fib(3) fib(4) fib(5) ] memo: {2: 1}
Compute fib(3) = fib(2) + fib(1); (1 from memo [ fib(4) fib(5) ] memo: {2: 1, 3: 2}
+ 1 from base case) Pop fib(3); update memo
Compute fib(4) = fib(3) + fib(2) (sum from what [ fib(5) ] memo: {2: 1, 3: 2, 4: 3}
is in the memo); Pop fib(4); update memo
Finally compute fib(5) = fib(4) + fib(3); sum memo: {2: 1, 3: 2, 4: 3, 5: 5}
from what is in the memo; Pop fib(5); update
memo. Recursion completes
Space and time complexity
analysis

Time Complexity:
· The time taken grows linearly depending on position of the Fibonacci
number to be returned. Hence, time complexity is O(n)

Space Complexity:
· The memory utilized will grow linearly depending on the size of the
Fibonacci number as this will vary the recursion stack size and the memo
table size. Therefore, the space complexity will be O(n)
Advantages and disadvantages
Advantages Disadvantages
· Massive Performance Gain - Eliminates redundant · Memory Overhead - Stores results of every
recalculations of the same subproblems. subproblem. Large problems may consume
significant memory.
· Simplicity and clarity - You retain the natural
· Recursive Stack Depth Limits - Still uses recursion
recursive structure of the problem i.e. easy to write,
hence risk of stack overflow for large inputs
read, and reason about.
· Possible Cache Management Complexity - You
· Automatic Overlapping Subproblem Handling - may need to manage when or how to clear/reset the
Memoization naturally handles overlapping cache. In memory-limited systems, uncontrolled
subproblems ;results are cached the first time and growth of memo can be problematic.
reused automatically.
· On-Demand Computation (Lazy Evaluation) - Only
computes subproblems that are actually needed.
· Reusability - Once computed, the cache (memo) can
be reused for other queries of the same function. This
can be beneficial in interactive or iterative algorithms.
Tabulation
 Does not use recursion
 Bottom-up approach
 Solves subproblems up to the final solution, starting with the base cases.
 The base cases are the initial and simplest subproblems
 Stores subproblems in a table e.g. an array or a map
 How it works
 Step 1: Initialize the Table
 Step 2: Initialize base cases
 Step 3: Perform iterative computation
 Step 4: Extract the final solution to the problem from the last subproblem
to be solved
Example - Fibonacci Sequence
 BEGIN
INPUT n

IF n < 2 THEN
RETURN n
ENDIF

Pseudocod CREATE array fib_array OF SIZE n + 1

SET fib_array [0] = 0

e
SET fib_array [1] = 1

FOR i FROM 2 TO n DO
fib_array[i] = fib_array[i - 1] + fib_array[i - 2]
ENDFOR

RETURN fib_array[n]
END
Flowchart
  Without dynamic programming
Time and  Using naive recursion, the complexity of Fibonacci
sequence implementation would be exponential (2^n)

Space  Each recursive call for element n of the sequence

makes two recursive calls: one to n-1 and one to n-2

complexity
 With dynamic programming (Tabulation)
 Time Complexity
 1 + 1 + 1 + 1 + 1 + n + 1 + n + 1 = 2n + 7 =
O(n)
 Time complexity = O(n)
 Space Complexity
 We create a single array of size n + 1
 n + 1 = O(n)
 Space complexity = O(n)
Optimization

 If the goal is just to return the

nth item of the Fibonacci
sequence, a variable of the
last computed subproblem
can be consistently used in
place of an array as the table
 This reduces the space
complexity from linear, O(n),
to constant, O(1)
Advantages and
Disadvantages
Advantages
 No Recursion - thus the program will never exceed allocated memory on the call
stack i.e. No Stack Overflow, even far large values of n
 Easier to Optimize Space
 When using a variable instead of an array for the subproblem storage, memory use of the
program for value storage will always be constant. Allowing efficient use of heap space
allocated to the program
 So, you can reduce from O(n) → O(1) space
 All subproblems are solved exactly once in a predictable sequence, avoiding the
overhead of repeated recursive calls.
 Memory and time are easier to estimate because every subproblem is visited once
 Disadvantages
 It solves all smaller subproblems, even if some aren’t required for the final answer
(Memoization solves only what’s needed.)
 Some problems (e.g. DFS for tree traversal problems) are easier to express
recursively.
Thank you🤝