Easy variation
Counting number of ways to reach sum X given N coins
simply build up fibonacci style where instead of manually hardcoding the n - 1 + n - 2, just put coins in an array and add each for each valid instance (adding memo[n-1])
observations
target: sum X iteration: iterate up to sum X choices each iteration: coins
What if you had to return the actual numbers used?
Answer (didn’t get immediately): backtracking
Question: is it better to store extra data while building or walk backward through finished iteration
I imagine that storing extra data during DP can get really expensive, so I’m going to educative guess walk backward.
I feel like recursively walking backward and checking what states were used doesn’t take too much compute, or at least is proportional to the actual DP algorithm, so it’s negligible in Big O.
Answer: Both work.
What if you had to return a list of all possible combinations of coins?
probably some sort of map where the value is overwritten throughout iteration
NVM: DP is not as good for enumeration because output size (understandably) can get huge.
But still could use DP with list of lists, treating like normal but now it keeps track of what coin used where. Create all possibilities after by backtracking?
What to use instead, if you really had to?
DP - merge (one result) DFS - explore (all combinations in this case) DFS still very expensive
What if you could only use each coin once?
still want to return number of ways to reach X, but only use coins once
Use 2-D DP
- have two cases for each where you use it or you don’t at a sum belonging to X
dp[coins][sum]
for i in range row size
for k in range col size
dp[i][k] = dp[i - 1][k] # preserving
if k - coins[i - 1] >= 0
can use coin
dp[i][k] += dp[i - 1][k - coins[i - 1]] # consider all possibilities of reaching last sum
still wouldn’t really work preserving number of ways should preserve from last row to carry over ways to reach sum from above in case where dont include current coin
At what point is it 2-D DP?
Look at constraints. If there a multiple constraints, then not 1D.
This is Knapsack 0-1! Usage constraints in addition to reach constraint.