Dynamic Programming
Missing line (or complete program) type questions
Question 1:
def fibonacci(n):
if n <= 1:
return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = _______________
return dp[n]
Options:
A. dp[i - 1] + dp[i - 2]
B. dp[i] + dp[i - 1]
C. dp[i] + dp[i - 2]
D. dp[i - 1] + dp[i - 1]
Correct Answer: A. dp[i - 1] + dp[i - 2]
Question 2:
def climbStairs(n):
if n <= 2:
return n
dp = [0] * (n + 1)
dp[1] = 1
dp[2] = 2
for i in range(3, n + 1):
dp[i] = _______________
return dp[n]
Options:
A. dp[i - 1] + dp[i - 2]
B. dp[i] + dp[i - 1]
C. dp[i - 1] + dp[i]
D. dp[i] + dp[i - 2]
Correct Answer: A. dp[i - 1] + dp[i - 2]
Question 3:
def minCostClimbingStairs(cost):
n = len(cost)
dp = [0] * (n + 1)
for i in range(2, n + 1):
dp[i] = _______________
return dp[n]
Options:
A. min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
B. max(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
C. min(dp[i] + cost[i - 1], dp[i - 2] + cost[i - 2])
D. max(dp[i - 1] + cost[i], dp[i - 2] + cost[i - 2])
Correct Answer: A. min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
Question 4:
def rob(nums):
if not nums:
return 0
if len(nums) == 1:
return nums[0]
dp = [0] * len(nums)
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, len(nums)):
dp[i] = _______________
return dp[-1]
Options:
A. max(dp[i - 1], dp[i - 2] + nums[i])
B. min(dp[i - 1], dp[i - 2] + nums[i])
C. max(dp[i - 1], dp[i - 2] + nums[i - 1])
D. min(dp[i - 1], dp[i - 2] + nums[i - 1])
Correct Answer: A. max(dp[i - 1], dp[i - 2] + nums[i])
Question 5:
def maxSubArray(nums):
dp = nums[:]
for i in range(1, len(nums)):
dp[i] = _______________
return max(dp)
Options:
A. max(nums[i], dp[i - 1] + nums[i])
B. min(nums[i], dp[i - 1] + nums[i])
C. max(nums[i], dp[i] + nums[i - 1])
D. min(nums[i], dp[i] + nums[i - 1])
Correct Answer: A. max(nums[i], dp[i - 1] + nums[i])
Question 6:
def maxProfit(prices):
max_profit = 0
for i in range(1, len(prices)):
if _______________:
max_profit += prices[i] - prices[i - 1]
return max_profit
Options:
A. prices[i] < prices[i - 1]
B. prices[i] > prices[i - 1]
C. prices[i] == prices[i - 1]
D. prices[i] <= prices[i - 1]
Correct Answer: B. prices[i] > prices[i - 1]
Question 7:
def countBits(n):
dp = [0] * (n + 1)
for i in range(1, n + 1):
dp[i] = _______________
return dp
Options:
A. dp[i >> 1] + (i & 0)
B. dp[i >> 1] + (i & 1)
C. dp[i << 1] + (i & 0)
D. dp[i << 1] + (i & 1)
Correct Answer: B. dp[i >> 1] + (i & 1)
Question 8:
def change(amount, coins):
dp = [0] * (amount + 1)
dp[0] = 1
for coin in coins:
for x in range(coin, amount + 1):
dp[x] += _______________
return dp[amount]
Options:
A. dp[x + coin]
B. dp[x - coin]
C. dp[x]
D. dp[x - coin] * coin
Correct Answer: B. dp[x - coin]
Question 9:
def uniquePaths(m, n):
dp = [[1] * n for _ in range(m)]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = _______________
return dp[-1][-1]
Options:
A. dp[i - 1][j] + dp[i][j - 1]
B. dp[i][j] + dp[i][j - 1]
C. dp[i][j] + dp[i - 1][j]
D. dp[i - 1][j] + dp[i - 1][j - 1]
Correct Answer: A. dp[i - 1][j] + dp[i][j - 1]
Question 10:
def longestCommonSubsequence(text1, text2):
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i - 1] == text2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = _______________
return dp[m][n]
Options:
A. max(dp[i - 1][j], dp[i][j - 1])
B. min(dp[i - 1][j], dp[i][j - 1])
C. max(dp[i][j], dp[i - 1][j])
D. min(dp[i][j], dp[i - 1][j])
Correct Answer: A. max(dp[i - 1][j], dp[i][j - 1])
Identify errors
Question 1:
def climbStairs(n):
if n <= 1:
return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
Options:
A. dp[i - 1] + dp[i - 2]
B. dp[i] + dp[i - 1]
C. dp[i] - dp[i - 2]
D. dp[i] * dp[i - 2]
Correct Answer: C. dp[i] - dp[i - 2]
Question 2:
def pascalsTriangle(numRows):
triangle = []
for row in range(numRows):
row = [1] * row
for j in range(1, row - 1):
row[j] = triangle[row - 1][j - 1] + triangle[row - 1][j]
triangle.append(row)
return triangle
Options:
A. triangle[row - 1][j - 1] + triangle[row - 1][j]
B. triangle[row - 1][j - 1] + triangle[row - 1][j + 1]
C. triangle[row][j - 1] + triangle[row - 1][j]
D. triangle[row - 1][j - 1] * triangle[row - 1][j]
Correct Answer: A. triangle[row - 1][j - 1] + triangle[row - 1][j]
Question 3:
def maxProfit(prices):
max_profit = 0
for i in range(1, len(prices)):
if prices[i] < prices[i - 1]:
max_profit += prices[i] - prices[i - 1]
return max_profit
Options:
A. prices[i] < prices[i - 1]
B. prices[i] > prices[i - 1]
C. prices[i] == prices[i - 1]
D. prices[i] <= prices[i - 1]
Correct Answer: B. prices[i] > prices[i - 1]
Question 4:
def countBits(n):
dp = [0] * (n + 1)
for i in range(1, n + 1):
dp[i] = dp[i >> 1] + (i & 0)
return dp
Options:
A. dp[i >> 1] + (i & 0)
B. dp[i >> 1] + (i & 1)
C. dp[i << 1] + (i & 0)
D. dp[i << 1] + (i & 1)
Correct Answer: B. dp[i >> 1] + (i & 1)
Question 5:
def isSubsequence(s, t):
dp = [[False] * (len(t) + 1)] * (len(s) + 1)
for i in range(1, len(s) + 1):
for j in range(1, len(t) + 1):
dp[i][j] = dp[i - 1][j - 1] and s[i - 1] == t[j - 1]
return dp[-1][-1]
Options:
A. dp[i - 1][j - 1] and s[i - 1] == t[j - 1]
B. dp[i][j] and s[i] == t[j]
C. dp[i - 1][j] and s[i] == t[j - 1]
D. dp[i][j - 1] and s[i - 1] == t[j]
Correct Answer: A. dp[i - 1][j - 1] and s[i - 1] == t[j - 1]
Question 6:
def divisorGame(N):
dp = [False] * (N + 1)
for i in range(1, N + 1):
dp[i] = not dp[i - 1]
return dp
Options:
A. dp[i] = not dp[i - 1]
B. dp[i] = dp[i - 1] + 1
C. dp[i] = dp[i - 1] * 2
D. dp[i] = dp[i - 1] / 2
Correct Answer: A. dp[i] = not dp[i - 1]
Question 7:
def nthTribonacci(n):
if n == 0:
return 0
if n == 1 or n == 2:
return 1
dp = [0] * (n + 1)
dp[1] = dp[2] = 1
for i in range(3, n + 1):
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
return dp[n]
Options:
A. dp[1] = dp[2] = 1
B. dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
C. dp[i] = dp[i - 1] + dp[i - 2]
D. dp[i] = dp[i - 1] * dp[i - 2]
Correct Answer: B. dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
Question 8:
def maxProfit(prices):
max_profit = 0
for i in range(1, len(prices)):
if prices[i] < prices[i - 1]:
max_profit += prices[i] - prices[i - 1]
return max_profit
Options:
A. prices[i] < prices[i - 1]
B. prices[i] > prices[i - 1]
C. prices[i] == prices[i - 1]
D. prices[i] <= prices[i - 1]
Correct Answer: B. prices[i] > prices[i - 1]
Question 9:
def countBits(n):
dp = [0] * (n + 1)
for i in range(1, n + 1):
dp[i] = dp[i >> 1] + (i & 0)
return dp
Options:
A. dp[i >> 1] + (i & 0)
B. dp[i >> 1] + (i & 1)
C. dp[i << 1] + (i & 0)
D. dp[i << 1] + (i & 1)
Correct Answer: B. dp[i >> 1] + (i & 1)
Question 10:
def minCostClimbingStairs(cost):
n = len(cost)
dp = [0] * (n + 1)
for i in range(2, n + 1):
dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
return dp[n]
Options:
A. min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
B. max(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
C. min(dp[i] + cost[i - 1], dp[i - 2] + cost[i - 2])
D. max(dp[i - 1] + cost[i], dp[i - 2] + cost[i - 2])
Correct Answer: A. min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
Identify output
Question 1
def func1(n):
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
print(func1(5))
What is the output of the code?
A) 3
B) 5
C) 8
D) 13
Answer: B) 5
---
Question 2
def func2(n):
if n == 0:
return 1
dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, n + 1):
for j in range(i, n + 1):
dp[j] += dp[j - i]
return dp[n]
print(func2(4))
What is the output of the code?
A) 3
B) 4
C) 5
D) 8
Answer: C) 5
---
Question 3
def func3(arr, n):
dp = [0] * (n + 1)
dp[0] = 1
for i in range(n):
for j in range(arr[i], n + 1):
dp[j] += dp[j - arr[i]]
return dp[n]
arr = [1, 2, 3]
n=4
print(func3(arr, n))
What is the output of the code?
A) 3
B) 4
C) 5
D) 7
Answer: B) 4
---
Question 4
def func4(n):
if n == 0:
return 0
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + 2 * dp[i - 2]
return dp[n]
print(func4(5))
What is the output of the code?
A) 7
B) 11
C) 15
D) 29
Answer: D) 29
---
Question 5
def func5(n):
if n == 0:
return 0
dp = [1] * (n + 1)
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
return dp[n]
print(func5(4))
What is the output of the code?
A) 4
B) 5
C) 7
D) 13
Answer: C) 7
---
Question 6
def func6(n):
if n == 0:
return 1
dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, n + 1):
for j in range(1, i + 1):
dp[i] += dp[i - j]
return dp[n]
print(func6(3))
What is the output of the code?
A) 4
B) 6
C) 7
D) 10
Answer: A) 4
---
Question 7
def func7(n):
dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, n + 1):
dp[i] = dp[i - 1] + 2 * dp[i - 2] if i >= 2 else 1
return dp[n]
print(func7(4))
What is the output of the code?
A) 5
B) 7
C) 9
D) 11
Answer: B) 7
---
Question 8
def func8(n):
dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, n + 1):
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] if i >= 3 else 1
return dp[n]
print(func8(5))
What is the output of the code?
A) 7
B) 9
C) 11
D) 13
Answer: B) 9
---
Question 9
def func9(n):
dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, n + 1):
for j in range(1, i + 1):
dp[i] += dp[i - j]
return dp[n]
print(func9(4))
What is the output of the code?
A) 8
B) 10
C) 15
D) 16
Answer: A) 8
Question 10
def func10(n):
dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, n + 1):
dp[i] = dp[i - 1] + (dp[i - 2] if i >= 2 else 0)
return dp[n]
print(func10(6))
What is the output of the code?
A) 8
B) 13
C) 21
D) 34
Answer: B) 13
Identify program to get the mentioned output
Question 1
Identify the program that outputs `13` for the input `6`.
A)
```python
def func1(n):
dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, n + 1):
dp[i] = dp[i - 1] + (dp[i - 2] if i >= 2 else 0)
return dp[n]
print(func1(6))
```
B)
```python
def func1(n):
dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, n + 1):
dp[i] = dp[i - 1] + (dp[i - 2] if i >= 2 else 1)
return dp[n]
print(func1(6))
```
C)
```python
def func1(n):
dp = [1] * (n + 1)
for i in range(1, n + 1):
dp[i] = dp[i - 1] + (dp[i - 2] if i >= 2 else 0)
return dp[n]
print(func1(6))
```
D)
```python
def func1(n):
dp = [1] * (n + 1)
for i in range(1, n + 1):
dp[i] = dp[i - 1] + (dp[i - 2] if i >= 2 else 1)
return dp[n]
print(func1(6))
```
Answer: A)
---
Question 2
Identify the program that outputs `5` for the input `4`.
A)
```python
def func2(n):
if n == 0:
return 1
dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, n + 1):
for j in range(i, n + 1):
dp[j] += dp[j - i]
return dp[n]
print(func2(4))
```
B)
```python
def func2(n):
if n == 0:
return 1
dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
print(func2(4))
```
C)
```python
def func2(n):
dp = [1] * (n + 1)
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
print(func2(4))
```
D)
```python
def func2(n):
if n == 0:
return 1
dp = [1] * (n + 1)
for i in range(1, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
print(func2(4))
```
Answer: A)
---
Question 3
Identify the program that outputs `9` for the input `5`.
A)
```python
def func3(n):
dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, n + 1):
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] if i >= 3 else 1
return dp[n]
print(func3(5))
```
B)
```python
def func3(n):
dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, n + 1):
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] if i >= 3 else 0
return dp[n]
print(func3(5))
```
C)
```python
def func3(n):
dp = [1] * (n + 1)
for i in range(1, n + 1):
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] if i >= 3 else 1
return dp[n]
print(func3(5))
```
D)
```python
def func3(n):
dp = [1] * (n + 1)
for i in range(1, n + 1):
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] if i >= 3 else 0
return dp[n]
print(func3(5))
```
Answer: A)
---
Question 4
Identify the program that outputs `8` for the input `4`.
A)
```python
def func4(n):
dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, n + 1):
for j in range(1, i + 1):
dp[i] += dp[i - j]
return dp[n]
print(func4(4))
```
B)
```python
def func4(n):
dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, n + 1):
for j in range(1, i + 1):
dp[i] += dp[i - 1]
return dp[n]
print(func4(4))
```
C)
```python
def func4(n):
dp = [1] * (n + 1)
for i in range(1, n + 1):
for j in range(1, i + 1):
dp[i] += dp[i - j]
return dp[n]
print(func4(4))
```
D)
```python
def func4(n):
dp = [1] * (n + 1)
for i in range(1, n + 1):
for j in range(1, i + 1):
dp[i] += dp[i - 1]
return dp[n]
print(func4(4))
```
Answer: A)
---
Question 5
Identify the program that outputs `5` for the input `4`.
A)
```python
def func5(n):
if n == 0:
return 0
dp = [1] * (n + 1)
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
return dp[n]
print(func5(4))
```
B)
```python
def func5(n):
if n == 0:
return 0
dp = [0] * (n + 1)
dp[0] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
return dp[n]
print(func5(4))
```
C)
```python
def func5(n):
if n == 0:
return 1
dp = [1] * (n + 1)
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
return dp[n]
print(func5(4))
```
D)
```python
def func5(n):
if n == 0:
return 1
dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, n + 1):
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
return dp[n]
print(func5(4))
```
Answer: A)
Basic to average to hard level conceptual questions
1. Which of the following is/are property/properties of a dynamic programming problem?
a) Optimal substructure
b) Overlapping subproblems
c) Greedy approach
d) Both optimal substructure and overlapping subproblems
View Answer
Answer: d
2. If an optimal solution can be created for a problem by constructing optimal solutions for its
subproblems, the problem possesses ____________ property.
a) Overlapping subproblems
b) Optimal substructure
c) Memoization
d) Greedy
View Answer
Answer: b
3. If a problem can be broken into subproblems which are reused several times, the problem
possesses ____________ property.
a) Overlapping subproblems
b) Optimal substructure
c) Memoization
d) Greedy
View Answer
Answer: a
4. If a problem can be solved by combining optimal solutions to non-overlapping problems, the
strategy is called _____________
a) Dynamic programming
b) Greedy
c) Divide and conquer
d) Recursion
View Answer
Answer: c
5. When dynamic programming is applied to a problem, it takes far less time as compared to other
methods that don’t take advantage of overlapping subproblems.
a) True
b) False
View Answer
Answer: a
6. A greedy algorithm can be used to solve all the dynamic programming problems.
a) True
b) False
View Answer
Answer: b
7. In dynamic programming, the technique of storing the previously calculated values is called
___________
a) Saving value property
b) Storing value property
c) Memoization
d) Mapping
View Answer
Answer: c
8. When a top-down approach of dynamic programming is applied to a problem, it usually
_____________
a) Decreases both, the time complexity and the space complexity
b) Decreases the time complexity and increases the space complexity
c) Increases the time complexity and decreases the space complexity
d) Increases both, the time complexity and the space complexity
View Answer
Answer: b
9. Which of the following problems is NOT solved using dynamic programming?
a) 0/1 knapsack problem
b) Matrix chain multiplication problem
c) Edit distance problem
d) Fractional knapsack problem
View Answer
Answer: d
10. Which of the following problems should be solved using dynamic programming?
a) Mergesort
b) Binary search
c) Longest common subsequence
d) Quicksort
View Answer
Answer: c
11. Which property of a problem suggests that it can be solved using Dynamic Programming?
a) Optimal substructure
b) Overlapping subproblems
c) Greedy approach
d) Both optimal substructure and overlapping subproblems
Answer: b
12. Which approach stores the solutions of subproblems so that they do not need to be recomputed?
a) Greedy approach
b) Recursive approach
c) Dynamic programming approach
d) Divide and conquer approach
Answer: c
13. What is the main characteristic of a problem with overlapping subproblems?
a) Solutions to subproblems are not reused
b) Solutions to subproblems are used repeatedly
c) Solutions to subproblems are never stored
d) Solutions to subproblems are computed only once
Answer: b
14. Which algorithmic strategy is NOT suitable for a problem without overlapping subproblems?
a) Memoization
b) Tabulation
c) Greedy approach
d) Recursive approach
Answer: c
15. Which technique involves storing precomputed values in a lookup table to reuse them for future
calculations?
a) Memoization
b) Recursion
c) Greedy approach
d) Bottom-up approach
Answer: a
16. What is the time complexity of the memoized Fibonacci function for computing fib(n)?
a) O(1)
b) O(log n)
c) O(n)
d) O(2^n)
Answer: c
17. Which programming approach starts solving the problem from the smallest subproblems and
builds up to the larger ones?
a) Bottom-up approach
b) Top-down approach
c) Recursive approach
d) Greedy approach
Answer: a
18. In dynamic programming, what is the space complexity typically associated with the tabulation
approach?
a) O(n)
b) O(1)
c) O(log n)
d) O(n^2)
Answer: a
19. Which problem-solving technique is NOT typically solved using dynamic programming?
a) Longest common subsequence
b) Matrix chain multiplication
c) Fractional knapsack problem
d) Binary search
Answer: d
20. Among the following sorting algorithms, which one is typically solved using dynamic programming?
a) Mergesort
b) Quicksort
c) Insertion sort
d) Bubble sort
Answer: a
21. What distinguishes dynamic programming (DP) from recursion?
a) DP solves problems by dividing them into smaller subproblems and stores solutions for reuse;
recursion calls a function within itself to achieve a task.
b) DP uses iterative techniques exclusively; recursion uses recursive techniques exclusively.
c) DP never uses recursion; recursion never uses DP.
d) DP and recursion are fundamentally the same.
Answer: a
22. Which principle characterizes the structure of the optimal solution in dynamic programming?
a) Recursive definition
b) Memoization
c) Optimal substructure
d) Tabulation
Answer: c
23. What is the purpose of memoization in dynamic programming?
a) To solve problems iteratively
b) To store solutions of subproblems for future use
c) To divide the problem into smaller subproblems
d) To eliminate the need for recursion
Answer: b
24. How does dynamic programming typically construct the optimal solution for a problem?
a) By recursively solving subproblems
b) By computing solutions using a greedy approach
c) By using memoization for all subproblems
d) By combining solutions to subproblems
Answer: d
25. Which approach in dynamic programming builds solutions from the smallest subproblems
upwards?
a) Recursive approach
b) Memoization approach
c) Bottom-up approach (Tabulation)
d) Top-down approach
Answer: c
26. Which of the following problems is typically solved using dynamic programming?
a) Binary search
b) Quick sort
c) Longest common subsequence
d) Bubble sort
Answer: c
27. What technique does dynamic programming use to avoid redundant computation?
a) Recursion
b) Memoization and tabulation
c) Greedy approach
d) Binary search
Answer: b
28. How does tabulation differ from memoization in dynamic programming?
a) Tabulation uses iterative approaches; memoization uses recursive approaches.
b) Memoization stores solutions in a lookup table; tabulation computes solutions iteratively from
smaller subproblems.
c) Tabulation is slower than memoization.
d) Memoization is a bottom-up approach; tabulation is a top-down approach.
Answer: b
29. Which technique in dynamic programming involves solving subproblems first and using their
solutions to build up to the main problem?
a) Recursive approach
b) Memoization approach
c) Bottom-up approach (Tabulation)
d) Top-down approach
Answer: c
30. What is the primary purpose of using dynamic programming?
a) To automate recursive functions
b) To solve optimization problems by dividing them into smaller subproblems
c) To eliminate recursion completely
d) To solve problems that involve direct computation without any division
Answer: b
