What is the recurrence for 0/1 Knapsack K[i][w] when weight $w_{i}$ > w?
When item i's weight exceeds current capacity w, it cannot be included, so K[i][w] equals K[i-1][w].
In Unbounded Knapsack (where items have infinite supply), what is the DP recurrence for K[w]?
With unlimited supply, item i can be chosen again, referencing K[w - $w_{i}$] from the current state rather than K[i-1].
What is the time complexity of Unbounded Knapsack for capacity W and n items?
For each capacity from 1 to W, we check up to n items, giving O(n * W) time.
Which of the following Dynamic Programming problems has a polynomial-time algorithm in the standard input-size model (rather than a pseudo-polynomial one)?
LCS has an O(m*n) algorithm polynomial in the input length. Standard DP formulations for 0/1 Knapsack, Subset Sum, and Partition are pseudo-polynomial because their running times depend on numeric capacities or target sums.
What is the number of subproblems in the DP formulation of Matrix Chain Multiplication for n matrices?
Subproblems correspond to matrix sub-chains $A_{i}$...$A_{j}$ for 1 <= i <= j <= n, which is n(n+1)/2 = $\Theta(n^2)$.