CSES Dynamic Programming (Knapsack Problems)

Pratik Tiwari
2 min readJan 1, 2021

Q1. https://cses.fi/problemset/task/1633/

Variant of Coin Change Problem
“For each i as target, count all possible ways using given coins”
dp[i] = All possible ways to get i using all coins

Q2. https://cses.fi/problemset/task/1634/

dp[i] = Minimum coins needed to achieve target = i using j coins

Q3. https://cses.fi/problemset/task/1635/

Similar to Q1, here we need all possible combination to get target value
Use same method as Q1.

Q4. https://cses.fi/problemset/task/1636

Compared to Q3, here we need only distinct combination (ordering is not important)
Example target = 5 , coins = (1,2,3)
(1,2,2) and (2,1,2) both will be counted in Q3
both are same in Q4 and counted only once