TC TCO05 Round 1 D1 500 (FibonacciSum)

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];
}