[go: up one dir, main page]
Scribd
Upload
2 views15 pages

Dynamic Programming[1]

Dynamic Programming (DP) is a technique for solving complex problems by breaking them into simpler overlapping subproblems, optimizing recursive algorithms by storing previously computed values. It has two main approaches: Top-Down (Memoization) and Bottom-Up (Tabulation), each with its own advantages. The document also discusses the Longest Common Subsequence (LCS) problem and provides pseudocode for its solution using DP.

Uploaded by

cabdulaahixussien
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
2 views15 pages

Dynamic Programming[1]

Dynamic Programming (DP) is a technique for solving complex problems by breaking them into simpler overlapping subproblems, optimizing recursive algorithms by storing previously computed values. It has two main approaches: Top-Down (Memoization) and Bottom-Up (Tabulation), each with its own advantages. The document also discusses the Longest Common Subsequence (LCS) problem and provides pseudocode for its solution using DP.

Uploaded by

cabdulaahixussien
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 15

Dynamic Programming

• Prepared by:
• Abdullahi Hussein Muhudin
• Muscap Ibraahim Abdulle
Introduction
• Dynamic Programming (DP) is a method for
solving complex problems by breaking them
into simpler subproblems. It is particularly
useful when these subproblems overlap and
the solution involves making optimal
decisions.
Why Use Dynamic Programming?
• Dynamic Programming is used to optimize
recursive algorithms by storing previously
computed values. It improves efficiency by
eliminating redundant calculations.
Key Properties of DP
• 1. Overlapping Subproblems: Subproblems are
solved multiple times.
• 2. Optimal Substructure: Optimal solution to a
problem can be constructed from optimal
solutions to its subproblems.
Overlapping Subproblems
• Overlapping subproblems occur when a
recursive algorithm solves the same
subproblems repeatedly. Dynamic
Programming stores the results of these
subproblems to avoid repeated work.
Optimal Substructure
• A problem has optimal substructure if an
optimal solution can be built from optimal
solutions of its subproblems. For example,
shortest path problems in graphs often have
this property.
DP Approaches
• There are two main approaches to
implementing DP:
• 1. Top-Down (Memoization)
• 2. Bottom-Up (Tabulation)
Top-Down Approach (Memoization)
• In this approach, we solve the problem
recursively and store the results of
subproblems in a table (usually a dictionary or
array). When the same subproblem is
encountered again, we return the stored value
instead of recalculating.
Example: Fibonacci using Memoization
• def fib(n, memo={}):
• if n <= 1:
• return n
• if n not in memo:
• memo[n] = fib(n - 1, memo) + fib(n - 2,
memo)
• return memo[n]
Bottom-Up Approach (Tabulation)
• In this approach, we solve all subproblems
first and store their results in a table. Then we
build up the solution to the main problem
using these stored values.
Fibonacci Tabulation – Step-by-Step
Example

• Example: Compute fib(6) using tabulation.


• Initial values: dp = [0, 1]

• Step-by-step:
• i = 2 → dp[2] = dp[1] + dp[0] = 1 + 0 = 1
• i = 3 → dp[3] = dp[2] + dp[1] = 1 + 1 = 2
• i = 4 → dp[4] = dp[3] + dp[2] = 2 + 1 = 3
• i = 5 → dp[5] = dp[4] + dp[3] = 3 + 2 = 5
• i = 6 → dp[6] = dp[5] + dp[4] = 5 + 3 = 8

• Final dp = [0, 1, 1, 2, 3, 5, 8]
• Return value: dp[6] = 8
Fibonacci: Top-Down vs Bottom-Up with
Print Output
• # Top-Down (Memoization)
• def fib_top_down(n, memo={}):
• if n in memo:
• print(f"Returning memo[{n}] = {memo[n]}")
• return memo[n]
• if n <= 1:
• return n
• memo[n] = fib_top_down(n - 1, memo) + fib_top_down(n - 2, memo)
• print(f"Computed fib({n}) = {memo[n]}")
• return memo[n]

• # Bottom-Up (Tabulation)
• def fib_bottom_up(n):
• dp = [0, 1]
• for i in range(2, n + 1):
• dp.append(dp[i - 1] + dp[i - 2])
• print(f"i = {i}, dp = {dp}")
• return dp[n]

• # Example when n = 5
• # Top-Down prints:
• Computed fib(2) = 1
• Computed fib(3) = 2
• Computed fib(4) = 3
• Computed fib(5) = 5

• # Bottom-Up prints:
• i = 2, dp = [0, 1, 1]
• i = 3, dp = [0, 1, 1, 2]
• i = 4, dp = [0, 1, 1, 2, 3]
• i = 5, dp = [0, 1, 1, 2, 3, 5]
Comparison: Memoization vs Tabulation

• Memoization:
• - Top-down approach
• - Uses recursion
• - Easier to implement

• Tabulation:
• - Bottom-up approach
• - Iterative
• - Often faster and more space-efficient
Longest Common Subsequence (LCS)
• LCS is the longest sequence that appears in
the same order in both strings. We use a 2D
DP table to find the length of LCS.
Longest Common Subsequence – Pseudocode
function LCS(X, Y):
m = length(X)
n = length(Y)
create dp[0...m][0...n] initialized to 0
for i from 1 to m:
for j from 1 to n:
if X[i-1] == Y[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]

You might also like