Problem Statement
Dynamic Programming (DP) is a method for solving complex problems by breaking them down into simpler overlapping subproblems and storing the results of these subproblems to avoid redundant calculations.
The goal is to find an efficient way to solve problems that can be broken down into similar subproblems, where each subproblem has a solution that depends on solutions to smaller subproblems.
Algorithmic Approach / Logic
A common approach to solving DP problems is to define a recursive function that computes the desired result for a given input. This function uses memoization or tabulation to store and reuse results of previously computed subproblems.
Memoization stores the results of expensive function calls and returns the cached result when the same inputs occur again. Tabulation, on the other hand, builds up solutions by solving smaller instances of the problem iteratively.
Code Implementation
def fibonacci(n):
# Base cases
if n == 0:
return 0
elif n == 1:
return 1
# Memoization array to store previously computed Fibonacci values
memo = [-1] * (n + 1)
def helper(n):
if memo[n] != -1:
return memo[n]
if n == 0:
memo[n] = 0
elif n == 1:
memo[n] = 1
else:
memo[n] = helper(n - 1) + helper(n - 2)
return memo[n]
return helper(n)Complexity Analysis
The time complexity of the above implementation is O(n), where n is the input number. This is because each Fibonacci number is computed only once, and the results are stored in a memoization array.
The space complexity is also O(n) due to the storage of previously computed Fibonacci numbers in the memoization array.