Given any number $n$, what is the method of finding out how many possible ways (unique) are there in which you can partition it - with the condition that all the numbers in each 'part' must be greater than or equal to 5.
e.g. say $n = 17$
So, $17$ can be written as:
$5 + 12$ (since the least number in each part must be 5)
$ 6 + 11 $
$ 7 + 10 $
$ 8 + 9 $ (same as $9 + 8$)
$ 5 + 6 + 6 $
$ 5 + 7 + 7 $
So $17$ can be partitioned in $7$ ways.
The question then is, what is the algorithm to find the number of all possible ways (the ways themselves aren't important)?
My way: use DP.
Let's say the function we are gonna write is $f$.
Calculate $f(5)$ ( $= 1$), remember it. Similarly calculate $f(6)...f(9)$
Now, coming to $f(10)$ from 10, at most we can cut off $5$ and hence $10 = 5 + 5$
Do this recursively and check for duplicates.
The problem with my method: But this seems a really naive algorithm and it seems to be slow (with all the checking of duplicates).
So, I am looking for some better method.