How many subproblems are solved in Tabulation for 0/1 Knapsack with n items and capacity W?
Table entries range from $i=0..n$ and $w=0..W$, totaling (n+1)(W+1) subproblems.
What is the cost of single source shortest path in a DAG with V vertices and E edges using Topological Order DP?
Topological sort takes O(V+E) and processing vertices in order takes O(V+E).
In Edit Distance, if the costs are insert=1, delete=1, and replace=2, what is this variation called?
When edit operations have non-unit costs, the metric is commonly described as weighted Levenshtein (edit) distance. Here insertion and deletion cost 1, while replacement costs 2.
What is the time complexity to solve the Egg Dropping puzzle for k eggs and n floors using Dynamic Programming?
Standard DP state E(k, n) = 1 + min_{1<=x<=n} max(E(k-1, x-1), E(k, n-x)) takes O(k * $n^2)$ time (can be optimized to O(k log n)).
In DP solution to Partition Equal Subset Sum problem, what must the sum of all array elements be?
To divide elements into two subsets of equal sum, total array sum must be even. Target = Total_Sum / 2.