6 articles
LC 322 Coin Change finds the minimum number of coins to make a target amount using unlimited coin supply. The recurrence dp[i] = min(dp[i - coin] + 1) over all coins is the canonical unbounded knapsack minimization problem, asked at Amazon, Google, and Microsoft as a core DP interview question.
LC 518 Coin Change II counts the number of combinations (not permutations) of coins that sum to a target amount. The key insight is the loop order: coins outer, amounts inner. This unbounded knapsack counting pattern is tested at Amazon and Google to distinguish candidates who understand loop-order reasoning from those who memorize templates.
LC 279 Perfect Squares finds the minimum number of perfect square integers that sum to n. It is isomorphic to Coin Change (LC 322) where the "coins" are all perfect squares up to n. The DP recurrence dp[i] = min(dp[i - j*j] + 1) runs in O(n * sqrt(n)) time and is asked at Google and Amazon.
LeetCode 416 Partition Equal Subset Sum is the cleanest 0/1 knapsack disguise on the platform. We reduce it to subset-sum-equals-half, derive the boolean DP recurrence, walk through the reverse-iteration trick, and finish with a one-liner bitset version that crushes interviews.
LeetCode 494 Target Sum looks like sign-assignment but reduces to subset-sum count via a beautiful algebra trick. We derive the reduction, build the 1D DP, dry-run a tabulation, and discuss why this O(n * sum) solution beats 2^n brute force at FAANG.
LeetCode 474 Ones and Zeroes is the cleanest two-capacity 0/1 knapsack on the platform. We derive the dp[i][j] recurrence, walk a full 2D table, and ship a 1D-collapsed solution that handles the dual-resource constraint while staying interview-friendly.