Integer Partition Count DP

Problem

The partition number p(n) counts unordered sums of positive integers adding to n, computed by the coin-change style recurrence p(n) = sum over parts of p(n - part).

Given n, return p(n).

Hint

Add parts one at a time to avoid double counting orders.

Test cases

case 1

in: [5]

expected: 7

case 2

in: [10]

expected: 42

case 3

in: [1]

expected: 1

Starter codePython

def integer_partition_count_dp(n):
    # Your code here
    pass

3 test cases · run your code against them in the editor