Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- In number theory and combinatorics, a partition of a positive integer n, also called an integer partition, is a way of writing n as a sum of positive integers. Two sums that differ only in the order of their summands are considered the same partition. If order matters, the sum becomes a composition. For example, 4 can be partitioned in five distinct ways:
- 4
- 3 + 1
- 2 + 2
- 2 + 1 + 1
- 1 + 1 + 1 + 1
- exp_sum(1) # 1
- exp_sum(2) # 2 -> 1+1 , 2
- exp_sum(3) # 3 -> 1+1+1, 1+2, 3
- exp_sum(4) # 5 -> 1+1+1+1, 1+1+2, 1+3, 2+2, 4
- exp_sum(5) # 7 -> 1+1+1+1+1, 1+1+1+2, 1+1+3, 1+2+2, 1+4, 5, 2+3
- exp_sum(10) # 42
- exp_sum(50) # 204226
- exp_sum(80) # 15796476
- exp_sum(100) # 190569292
- =====================================================================================================================================
- @solution:
- import operator
- get_last_item = operator.itemgetter(-1)
- def exp_sum(n):
- p_matrix=[[0]*(n+1) for x in range(n+1)]
- # return p_matrix
- for i in range(0,n+1):
- p_matrix[i][0]=1
- for i in range(1,n+1):
- for j in range(1,n+1):
- if i>j:
- p_matrix[i][j]=p_matrix[i-1][j]
- else:
- exclude_i=p_matrix[i-1][j]
- include_i=p_matrix[i][j-i]
- p_matrix[i][j]=exclude_i+include_i
- return p_matrix[n][-1]
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement