Provide an example of Dynamic Program but without Recursion

Dynamic programming (DP) can be implemented without recursion by using an iterative approach, often referred to as the bottom-up method or tabulation. This approach involves solving smaller subproblems first and using their solutions to build up the solution to the larger problem. Here is an example of solving the Fibonacci sequence using dynamic programming without recursion.

Example: Fibonacci Sequence

The Fibonacci sequence is defined as:
$$ F(n) = F(n-1) + F(n-2) $$
with base cases:
$$ F(0) = 0 $$
$$ F(1) = 1 $$

Iterative Dynamic Programming Solution

def fibonacci(n):
    if n <= 1:
        return n
    
    # Initialize base cases
    fib = [0] * (n + 1)
    fib[0] = 0
    fib[1] = 1
    
    # Build the table in a bottom-up manner
    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} is {fibonacci(n)}")

Explanation

1. Initialization: We start by initializing an array fib of size $$ n+1 $$ to store the Fibonacci numbers. The base cases are set as fib = 0 and fib[1] = 1.

2. Iteration: We then iterate from 2 to $$ n $$, filling in the array using the relation $$ fib[i] = fib[i-1] + fib[i-2] $$.

3. Result: Finally, the $$ n $$-th Fibonacci number is returned from the array.

This approach avoids the overhead of recursive function calls and is more space-efficient than a naive recursive solution with memoization, especially for large $$ n $$. The time complexity of this solution is $$ O(n) $$, and the space complexity is also $$ O(n) $$ due to the array used to store the Fibonacci numbers.

This example demonstrates how dynamic programming can be effectively used without recursion by employi...