**Category:**Greedy, Dynamic Programming

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

The problem asks us to compute the minimum number of Fibonacci numbers required to sum up to a given number n. If you are familiar with Zeckendorf's Theorem then you might be able to see a greedy strategy. Zeckendorf's Theorem states that every positive integer can be represented in a unique way as the sum of one or more distinct Fibonacci numbers such that it does not contain two consecutive Fibonacci numbers. A more obvious approach is to use dynamic programming, let D(n) denote the minimum number of Fibonacci terms to make up a sum of exactly n. Then we can define a recurrence relation such as: F(n) = min { 1 + F(n - T[k]) } where T[k] denotes the k-th Fibonacci term. Obviously F(n - T[k]) is only defined for n - T[k] >= 0. Additionally, the base case is defined as F(0) = 0, which acts as our stopping point as this means we have no remaining sum to make up for. Coding this is relatively simple:

class FibonacciSum { public: int howMany(int); }; int tab[101]; int memo[1000001]; int cnt; #define INF (1 << 20) int func(int n) { int res = INF; if (n == 0) return 0; if (memo[n] != -1) return memo[n]; for (int i = cnt; i >= 0; i--) { if (n - tab[i] >= 0) res <?= 1 + func(n - tab[i]); } return memo[n] = res; } int FibonacciSum::howMany(int n) { tab[0] = tab[1] = 1; cnt = 2; memset(memo,-1,sizeof(memo)); for (int i = 2; tab[i-1] + tab[i-2] < 1000000; i++, cnt++) { tab[i] = tab[i-1] + tab[i-2]; } cnt--; return func(n); }

We can also translate this into a bottom-up dynamic programming algorithm. To do this, we must consider the order of calculation - this is dictated by the recurrence relation we defined earlier. As this is a 1 dimensional DP problem, it's relatively simple: given an n value, we need to compute all values below n before considering n. This can be seen by the term inside the recursive call (n - T[k]), as T[k] is strictly positive for all k values we are guaranteed to only require all values below n to be calculated beforehand.

class FibonacciSum { public: int howMany(int); }; int dp[1000001]; int tab[101]; #define INF (1 << 20) int FibonacciSum::howMany(int n) { tab[0] = tab[1] = 1; int cnt = 2; for (int i = 2; tab[i-1] + tab[i-2] < 1000000; i++, cnt++) { tab[i] = tab[i-1] + tab[i-2]; } dp[0] = 0; for (int i = 1; i <= n; i++) { dp[i] = INF; for (int k = 1; k < cnt; k++) { if (i - tab[k] < 0) break; dp[i] = min(dp[i], 1 + dp[i - tab[k]]); } } return dp[n]; }

## No comments:

## Post a Comment