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