Dynamic Programming

Sample Code

dp = [0] * (W + 1)
for weight in weights:
    for w in range(W, weight - 1, -1):
        dp[w] = max(dp[w], dp[w - weight] + value)

tutorial video :

• https://www.youtube.com/watch?v=kvyShbFVaY8

Easy (Knapsack Basics)

1. 416. Partition Equal Subset Sum

2. 494. Target Sum

3. 1049. Last Stone Weight II

Medium (Classic 0/1 Knapsack)

1. 474. Ones and Zeroes

2. 322. Coin Change (0/1 variant when restricted)

3. 518. Coin Change II

4. 879. Profitable Schemes