Подсчет уникальных наборов?

Question

Я решал эту проблему: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=286&page=show_problem&problem=3268
и я застрял и не нашел подсказок.
Вопрос:

You will be given an integer n (n<=10^9) now you have to tell how many 
distinct sets of integers are there such that each number from 1 to n can 
be generated uniquely from a set. Also sum of set should be n. eg for n=5 , one such set is: 
{1,2,2} as 
1 can be generated only by { 1 } 
2 by { 2 } 
3 by {1,2} (note the two 2's are indistinguishable) 
4 by {2,2} 
5 by {1,2,2} 
for generating a number each number of a set can be used only once. ie for above set 
we can't do {1,1} to generate 2 as only one 1 is there. 
Also the set {1,2,2} is equivalent to {2,1,2} ie sets are unordered. 

Мой подход:

The conclusion I came to was. Let F(S,k) denote number desired sets of sum S whose 
largest element is k.Then to construct a valid set we can take two paths from this 
state.Either to F(S+k,k) or to F(2*S+1,S+1).I keep a count of how many times I come 
to state where S=n(the desired sum) and do not go further if S becomes > n.This is 
clearly bruteforce which I just wrote to see if my logic was correct(which is correct) 
.But this will give time limit exceed . How do I improve my approach??I have a 
feeling it is done by dp/memoization. 

Answer 1

Это известное число последовательности.

Спойлеры: http://oeis.org/A002033