Fibonacci-style

(i).Fibonacci -Recursive

Python Code


def fibonacci_recursive(n):
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)

(ii). Fibonacci - Memoization(TOP DOWN)

Python Code


def fibonacci_memoized(n):
    memo = {}
    
    def fib(n):
        if n in memo:
            return memo[n]
        if n <= 0:
            memo[n] = 0
        elif n == 1:
            memo[n] = 1
        else:
            memo[n] = fib(n - 1) + fib(n - 2)
        return memo[n]
    
    return fib(n)

# Example usage
print(fibonacci_memoized(10))

(iii). Fibonacci - Tabulation(Bottom UP)

Python Code


def fibonacci_bottom_up(n):
    if n <= 1:
        return n
    
    fib = [0] * (n + 1)
    fib[1] = 1
    
    for i in range(2, n + 1):
        fib[i] = fib[i - 1] + fib[i - 2]
    
    return fib[n]

# Example usage
n = 10
result = fibonacci_bottom_up(n)
print(f"The {n}-th Fibonacci number is: {result}")

1. Climbing Stairs


if n == 0: return 0
if n == 1: return 1
        
dp = [0]*(n+1)
dp[1] =1
dp[2] =2
for i in range(3,n+1):
    dp[i] = dp[i-1] + dp[i-2]
print(dp[n])

2. Equal Sum Partition

Python Code


def EqualSumPartition(arr,n,sm):
    dp = [[False for _ in range(sm+1)]for _ in range(n+1)]
    for i in range(n+1):
        dp[i][0] = True
    for i in range(1,sm+1):
        dp[0][i] = False
        
    for i in range(1,n+1):
        for j in range(1,sm+1):
            if arr[i-1]<=j:
                dp[i][j] = dp[i-1][j - arr[i-1]] or dp[i-1][j]
            else:
                dp[i][j] = dp[i-1][j]
    return dp[n][sm]
    
arr = [1,5,11,5,1]
sm =sum(arr)
if sm%2==0:
    res = subsetSum(arr,len(arr),sm//2)
    print(res)
else:
    print(False)

3. Count of subset sum

Python Code


def count(arr,n,sum):


    dp = [[0]*(sum+1) for _ in range(n+1)]
            
    for i in range(0,n+1):
        dp[i][0] =1
    for i in range(1,n+1):
        for j in range(sum+1):
            if arr[i-1]<=j:
               dp[i][j] = dp[i-1][j - arr[i-1]] + dp[i-1][j]
           else:
               dp[i][j] = dp[i-1][j]
    return dp[-1][-1]%mod

arr = [1,2,3,4]
n = len(arr)
res = count(arr,n,sum(arr))
print(res)