[HELP NEEDED] Why does these solutions for CSES Coin Combination 1 & 2 work ?

Правка en2, от Rainman84, 2021-05-24 07:28:48

To brush up on my DP skills I decided to solve some problems from the topic from CSES.

I came across 2 problems of very similar solutions: Coin Combinations I and Coin Combinations II.

In the first problem, the order of the coins matter and in the second version, it does not.

Code for 1st problem
Code for 2nd Problem

What's interesting is that both these solutions are basically the same, the only difference being the order of the for loops reversed. This is where I am confused. I tried to run a few test cases by hand and managed to understand how this code works but I can't figure out why this code works the way it does.

I have a very foggy intuition about the 2nd one, wherein I am visualizing how every coin $$$c_i$$$ contributes to a particular sum (much like the sieve algorithms), But I may be wrong.

Any Help would be greatly appreciated :).

Теги #dynamic programing, #cses

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский Rainman84 2021-05-24 07:28:48 1083 (published)
en1 Английский Rainman84 2021-05-24 07:19:05 908 Initial revision (saved to drafts)