In dynamic programming, the value of an optimal solution is computed using a bottom-up or top-down approach, depending on the specific problem and its characteristics.
Consider example of calculating fibonacci Series.
Top Down – here we start with the original problem and recursively break it down into smaller subproblems. However, you avoid redundant computations by memoizing (caching) the solutions to subproblems.
e.g
def fibonacci(n, memo={}): //memo is dictionary used to store the solutions to subproblems,
if n in memo:
return memo[n]
if n <= 1:
result = n
else:
result = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
memo[n] = result
return result
# Example usage:
result = fibonacci(5)
print(result)
we can solve again with bottom up i.e solving smaller subproblems first and building up to the solution of the original problem.
e.g
def fibonacci_bottom_up(n):
if n <= 1:
return n
# Initialize an array to store Fibonacci numbers
fib = [0] * (n + 1)
fib[1] = 1
# Calculate Fibonacci numbers from bottom up
for i in range(2, n + 1):
fib[i] = fib[i - 1] + fib[i - 2]
return fib[n]
# Example usage:
result_bottom_up = fibonacci_bottom_up(5)
print(result_bottom_up)
So Correct Answer will be Both A and B.