diff options
| author | mo <mokha@cisco.com> | 2017-07-25 19:59:51 -0600 |
|---|---|---|
| committer | mo <mokha@cisco.com> | 2017-07-25 19:59:51 -0600 |
| commit | cc1c83ec768d60d01181a58f8395de04081ea7cd (patch) | |
| tree | 2fa2b8eefcf2cbac6acc8278d455f1eb2a89c262 | |
| parent | 76b665f86866689ff3f972ca2bc37c84e6d06ae8 (diff) | |
use dp solution.
| -rw-r--r-- | spec/possible_sums_spec.rb | 23 |
1 files changed, 21 insertions, 2 deletions
diff --git a/spec/possible_sums_spec.rb b/spec/possible_sums_spec.rb index 3b6c57f..2e868c6 100644 --- a/spec/possible_sums_spec.rb +++ b/spec/possible_sums_spec.rb @@ -1,5 +1,6 @@ <<-DOC -You have a collection of coins, and you know the values of the coins and the quantity of each type of coin in it. You want to know how many distinct sums you can make from non-empty groupings of these coins. +You have a collection of coins, and you know the values of the coins and the quantity of each type of coin in it. +You want to know how many distinct sums you can make from non-empty groupings of these coins. Example @@ -49,7 +50,25 @@ DOC describe "#possible_sums" do def possible_sums(coins, quantity) - 0 + maximum = coins.zip(quantity).map { |(x, y)| x * y }.sum + + dp = [false] * (maximum + 1) + dp[0] = true + + coins.zip(quantity).each do |(coin, q)| + (0...coin).each do |b| + num = -1 + (b..maximum + 1).step(coin).each do |i| + if dp[i] + num = 0 + elsif num >= 0 + num += 1 + end + dp[i] = (0 <= num && num <= q) + end + end + end + dp.map { |x| x ? 1 : 0 }.sum - 1 end [ |