CODEWITHSUNDEEP
algorithmdynamic-programming
Sky
Sky

Reputation: 79

Different ways to sum a number using numbers less than or equal to k

Example: Given total = 8 and k = 2, the number of different ways of represent 8 as the sum of integers between 1 and 2, inclusive, is 5 ways:

[1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 2]
[1, 1, 1, 1, 2, 2]
[1, 1, 2, 2, 2]
[2, 2, 2, 2]

Constrains:

1 <= total <= 1000
i <= k <= 100

How can we solve this problem? Dynamic programming?

Upvotes: 2

Views: 5453

Answers (1)

btilly
btilly

Reputation: 46399

In an interview, if you suspect that a problem might be dynamic programming, you should immediately write it as a recursive function, then add caching (aka memoizing).

So what are our base cases?

  1. total is 0. In which case an empty sum does it.

  2. total < 0. In which case there is no way to do it.

  3. The range of numbers we are considering is empty. In which case there is no way to do it.

In every other case we either reduce the size of our list, or else use the largest number of our list.

This recursive solution is very straightforward.

def ways_to_sum(total, lower, upper):
    if total < 0:
        return 0
    elif total == 0:
        return 1
    elif upper < lower:
        return 0
    else:
        return ways_to_sum(total - upper, lower, upper) + ways_to_sum(total, lower, upper - 1)

print(ways_to_sum(8, 1, 2)) # prints 5
print(ways_to_sum(800, 1, 5)) # locks up

Now the problem with this is that we do a lot of work over and over again. Therefore we add caching:

cached_ways_to_sum = {}
def ways_to_sum(total, lower, upper):
    if total < 0:
        return 0
    elif total == 0:
        return 1
    elif upper < lower:
        return 0
    else:
        key = (total, lower, upper)
        if key not in cached_ways_to_sum:
            cached_ways_to_sum[key] = ways_to_sum(total - upper, lower, upper) + \
                                      ways_to_sum(total, lower, upper - 1)
        return cached_ways_to_sum[key]

print(ways_to_sum(8, 1, 2)) # prints 5
print(ways_to_sum(800, 1, 5)) # prints 147624812

If at that point you are asked for another way to do it, only then should you consider doing a bottom up DP solution. And even then, I consider what winds up in the cache and build it from that.

Upvotes: 6

Related Questions