recategorized by
630 views

3 Answers

1 votes
1 votes

Two approaches:

  • Top down: memoize recursion
  • Bottom up: find and store optimal solutions to subproblems, then use stored solutions to find optimal solution to problem

Correct Answer is A,B

edited by
0 votes
0 votes
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.
Answer:

Related questions

1 votes
1 votes
1 answer
1
gatecse asked Dec 9, 2020
653 views
Which of the following is a correct time complexity to solve the $0/1$ knapsack problem where $n$ and $w$ represents the number of items and capacity of knapsack respecti...
1 votes
1 votes
1 answer
2
gatecse asked Dec 9, 2020
717 views
Assembly line scheduling and Longest Common Subsequence problems are an example of _______.Dynamic ProgrammingGreedy AlgorithmsGreedy Algorithms and Dynamic Programming r...