Algorithms Dynamic Programming & Optimization 1

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

Dynamic programming applies when a problem has optimal substructure (optimal solution built from optimal sub-solutions) and overlapping subproblems (same subproblems recur).

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

The 0/1 Knapsack DP fills an n×W table where each cell takes O(1) time, giving O(nW) overall complexity.

Question 3

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

Accepted Answer

Longest Common Subsequence

Answer

The Longest Common Subsequence (LCS) problem finds the longest sequence present in both strings in the same order, solved in O(mn) by DP.

Question 4

What is memoization in the context of dynamic programming?

Accepted Answer

Caching results of subproblems to avoid redundant computation

Answer

Memoization stores the result of each subproblem the first time it is solved so future calls return the cached answer immediately.

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

Naive recursive Fibonacci recomputes subproblems exponentially (O(2ⁿ)), while DP computes each of the n values exactly once in O(n) time.

Algorithms Practice Test

Algorithms Practice Test

Algorithms Dynamic Programming & Optimization 1