TCS NQT Guide TCS NQT Coding Capability & AlgorithmsDynamic Programming: Coin Change and 0/1 Knapsack Problem

Dynamic Programming: Coin Change and 0/1 Knapsack Problem

Learn core concepts, essential formulas, and attempt practice questions designed on the latest TCS NQT testing patterns.

Key Concepts & Formulas

1DP: Solve overlapping subproblems and store their results (Memoization / Tabulation).
20/1 Knapsack: Choose item (include) or skip item (exclude) to maximize value within weight limit.

Practice Question 1

What is the difference between Memoization and Tabulation?

A) Memoization is Top-Down; Tabulation is Bottom-Up

B) Memoization is Bottom-Up; Tabulation is Top-Down

C) Memoization is faster

D) No difference

Correct Answer: A) Memoization is Top-Down; Tabulation is Bottom-Up

Step-by-step Solution: Memoization caches recursive call results (Top-Down). Tabulation builds lookup tables iteratively (Bottom-Up).

Practice Question 2

In 0/1 Knapsack, can we take fractional parts of items?

A) No, items must be chosen completely or skipped

B) Yes, always

C) Only if value is high

D) Depends on weight limit

Correct Answer: A) No, items must be chosen completely or skipped

Step-by-step Solution: The '0/1' name indicates binary choices: either include the item completely (1) or skip it (0).

Write down the DP state transition formula before writing code loops.