Trobule understanding optimal solution in CodeAgon from Hackerrank

Revision en1, by iCanCodeBro, 2017-09-03 12:57:03

In this problem I am having trouble understanding why we use concept like sliding window instead of trying all combinations+DP ? Especially the bold line in below paragraph which is from the Editorial.

However, the second sample test case shows that when n>m there is a possibility that purchasing items from the first m shops will take more time than skipping one or more shops. We'll need to calculate the amount of time for each possible combination of shops and choose the combination that takes the least amount of time. It's important that we can calculate all of these times optimally. If we were to create an array of each of the combinations and then use the loop above for each combination, we'd be forgetting that each combination is only different from the next by one shop.

Can you please explain proof for the statement ?

Pseudo codes from editorial here.

Thanks.

Tags #hackerrank, #dp, proof

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English iCanCodeBro 2017-09-03 12:57:03 1070 Initial revision (published)