Which statement about dynamic programming and a classic knapsack problem is correct?

• A. DP is a greedy method that does not reuse subproblem results
• B. DP solves optimization by storing subproblem solutions; classic knapsack recurrence dp[i][w] = max(dp[i-1][w], value_i + dp[i-1][w - weight_i])
• C. DP uses divide-and-conquer with no memoization
• D. DP enumerates all subsets without reuse of subproblem results

Answer: (B)

Dynamic programming solves optimization problems by storing solutions to overlapping subproblems and reusing them to build larger results. In the classic 0/1 knapsack, you describe a table where the entry for the first i items and capacity w represents the best value you can achieve. To fill this entry, you consider two possibilities: skip the i-th item or take it (if it fits). The optimal value is the maximum of these two possibilities, which yields the recurrence dp[i][w] = max(dp[i-1][w], value_i + dp[i-1][w - weight_i]). This directly shows reusing subproblem results: both options rely on solutions to smaller subproblems (fewer items and smaller remaining capacity).

This is what makes it dynamic programming: it avoids brute-force subset enumeration and leverages previously solved subproblems. It’s not a greedy method, which makes decisions step by step without guaranteeing global optimality, and it’s not plain divide-and-conquer with no memoization, which wouldn’t reuse results.