CSES Dynamic Programming (Knapsack Problems)
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