My QA Projects

title: 10_Algorithms - Dynamic Algorithms layout: default —

Dynamic Programming:

Fibonacci Series:

Classic example demonstrating memoization (top-down) or tabulation (bottom-up) approaches to optimize recursive solutions.

memoization (top-down)

storing the results of expensive function calls and reusing them when the same inputs occur again.

# Memoization using a dictionary to store computed values
memo = {}

def fibonacci_memo(n):
    if n in memo:
        return memo[n]
    if n <= 1:
        result = n
    else:
        result = fibonacci_memo(n-1) + fibonacci_memo(n-2)
    memo[n] = result
    return result

# Example usage:
n = 10
print(f"Fibonacci number at position {n}: {fibonacci_memo(n)}")

'''
The function fibonacci_memo checks if the Fibonacci number for n has already been computed and stored in memo.
If n is less than or equal to 1, it returns n.
Otherwise, it recursively calculates Fibonacci numbers using previously computed results stored in memo.
'''

tabulation (bottom-up)

starts from the smallest subproblem and builds up solutions for larger subproblems using an iterative approach.

def fibonacci_tabulation(n):
    if n <= 1:
        return n
    
    # Initialize a list to store Fibonacci numbers from 0 to n
    fib = [0] * (n + 1)
    fib[1] = 1
    
    # Build the Fibonacci sequence iteratively
    for i in range(2, n + 1):
        fib[i] = fib[i-1] + fib[i-2]
    
    return fib[n]

# Example usage:
n = 10
print(f"Fibonacci number at position {n}: {fibonacci_tabulation(n)}")

'''
The function fibonacci_tabulation initializes a list fib to store Fibonacci numbers from 0 to n.
It iteratively calculates each Fibonacci number from 2 to n using the sum of the two preceding numbers (fib[i-1] and fib[i-2]).
Finally, it returns the Fibonacci number at position n.

'''

Comparison:

Memoization (Top-Down): Efficiently handles recursion by storing computed results, reducing redundant calculations. It is easier to implement when starting from a recursive approach.

Tabulation (Bottom-Up): Uses an iterative approach to compute results from smaller subproblems to larger ones. It avoids the overhead of function calls and recursion limits but may require more space for storage.

Both approaches improve the time complexity of the naive recursive solution (O(2^n)) to O(n) for both memoization and tabulation, making them much more efficient for calculating Fibonacci numbers, especially for larger values of n.

Longest Common Subsequence (LCS):

Dynamic programming approach to finding the longest subsequence common to two sequences.

Knapsack Problem:

Optimization problem where items have both weight and value constraints, and the goal is to maximize value without exceeding the weight capacity.

Dynamic Programming:

Comparison: