TopCoder problem "FibonacciSum" used in TCO05 Round 1 (Division I Level Two)



Problem Statement

    Depicted below is the Fibonacci sequence:
   1, 1, 2, 3, 5, 8, 13, 21, 34, ...
As you can see, each value from 2 on is the sum of the previous two values. Any positive integer can be written as a sum of values taken from the Fibonacci sequence. These values need not be distinct. Return the smallest number of such values that sum to n.
 

Definition

    
Class:FibonacciSum
Method:howMany
Parameters:int
Returns:int
Method signature:int howMany(int n)
(be sure your method is public)
    
 

Constraints

-n will be between 1 and 1000000 inclusive.
 

Examples

0)
    
1
Returns: 1
Just a single number is required.
1)
    
7
Returns: 2
The best we can do is 5+2 = 7.
2)
    
70
Returns: 3
The best here is 34+34+2 = 70.
3)
    
107
Returns: 3

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=4629

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8019&pm=4629

Writer:

AdminBrett

Testers:

PabloGilberto , lbackstrom , vorthys , Olexiy

Problem categories:

Dynamic Programming, Greedy