In the song "The Twelve Days of Christmas," a total of 364 gifts are given. However, the majority of those gifts are of living things (turtle doves, maids a milking, etc). Don't those creatures deserve gifts too? Then how many gifts would there be?
This is a programming problem to find the answer. Assume that every gift given get all of the gifts of a lower number than it (ex. a French hen gets two turtle doves and a partridge in a pear tree). Those gifts also need gifts though (ex. those two turtle doves also get their own partridges in pear trees), and so on, all the way down. Golden rings however, being inanimate objects, do not need any gifts. Additionally, partridges in pear trees do not get any gifts, as they are the first gift. With all of these additional gifts, how many gifts would be given in total through the course of the song?
- Dynamic programming is going to be your friend here
- First figure out how to calculate the 364 gifts in the normal version of the song, then build off of that