Use recursive to solve it:
if pieces < people: return 0 if people == 1 or pieces == people: return 1
return piemap[(pieces, people)] =
pie(pieces - 1, people - 1) + pie(pieces - people, people)
n = int(input())
k = int(input())
piemap = dict()
def pie(pieces, people):
if pieces < people:
return 0
if people == 1 or pieces == people:
return 1
return pie(pieces - 1, people - 1) + pie(pieces - people, people)
DP1 solution:
save the above middle result, then do recursive
n = int(input())
k = int(input())
piemap = dict()
def pie(pieces, people):
if pieces < people:
return 0
if people == 1 or pieces == people:
return 1
if (pieces, people) in piemap:
return piemap[(pieces, people)]
piemap[(pieces, people)] = pie(pieces - 1, people - 1) + pie(pieces - people, people)
return piemap[(pieces, people)]
print(pie(n, k))DP2 solution:
way[i][j] = way[i-1][j-1] + way[i-j][j]
pizza = int(input())
people = int(input())
way = [[0 for i in range(people+1)] for i in range(pizza+1)]
way[0][1] = 1
for i in range(1, pizza+1):
for j in range(1, min(people, i)+1):
way[i][j] = way[i-1][j-1] + way[i-j][j]
print(way[pizza][people])
print(pie(n, k))
Comments