Algorithms Dynamic Programming & Optimization

Question 1

What are the two key properties a problem must have to be solvable with dynamic programming?

Accepted Answer

Optimal substructure and overlapping subproblems

Answer

Linearity and monotonicity

Answer

Greedy choice and independence

Answer

Recursion and memoization

Question 2

What is the time complexity of the classic 0/1 Knapsack DP solution with n items and capacity W?

Accepted Answer

O(nW)

Answer

O(n + W)

Answer

O(n log W)

Answer

O(n²)

Question 3

Which DP problem asks for the length of the longest subsequence common to two strings?

Accepted Answer

Longest Common Subsequence

Answer

Longest Increasing Subsequence

Answer

Edit Distance

Answer

Coin Change

Question 4

What is memoization in the context of dynamic programming?

Accepted Answer

Caching results of subproblems to avoid redundant computation

Answer

Sorting subproblems before solving

Answer

Converting recursion to iteration

Answer

Splitting the problem into independent parts

Question 5

In the Fibonacci sequence computed with DP, what is the time complexity compared to naive recursion?

Accepted Answer

DP is O(n) vs naive O(2ⁿ)

Answer

Both are O(2ⁿ)

Answer

DP is O(n²) vs naive O(n)

Answer

Both are O(n)

Question 6

What approach does the Coin Change problem use to find the minimum number of coins for a target amount?

Accepted Answer

Bottom-up DP filling amounts from 0 to target

Answer

Greedy selection of largest coin

Answer

Binary search on coin values

Answer

Divide and conquer on coin denominations