runtimequestion 370 Profiling & Optimization · hard
Ways to pay an amount, with a cache
A self-checkout suggests how many different combinations of coins and notes can pay an amount (order doesn't matter: 2 + 5 and 5 + 2 are one way). The natural recursion: the ways to pay amount with denominations from position i on are the ways that use denominations[i] at least once plus the ways that skip it. Without a cache this repeats subproblems exponentially; write ways_to_pay(amount, denominations) with one.
Function
ways_to_pay(amount, denominations)Inputsa whole-number amount in cents (≥ 0) and a list of distinct positive denominations
Returnsthe number of combinations;
1 for an amount of 0 (pay nothing), 0 if it can't be paidConstraint300 cents with 8 denominations must answer within the time limit
Examples
callways_to_pay(5, [1, 2, 5])returns4
callways_to_pay(10, [2, 5, 3, 6])returns5
callways_to_pay(0, [1])returns1