[CareerCup][Google Interview] 打印所有的Binary Number

If the Fibonacci series is 1,2,3,5,8,13,….. then 10 can be written as 8 + 2 ==> 10010 and 17 can be written as 13 + 3 + 1 ==> 100101. Got it?? The Question was, given n, I need to get all possible representations of n in Fibonacci Binary Number System. as 10 = 8 + 2 ==> 10010 also 10 = 5 + 3 + 2 ==> 1110

这里8+2= 10,

1 2 3 5 8 13

0 1 0 0 1 -->二进制数为10010

DP来解决，复杂度O(n * n * m), m是给的数，n是小于m的fib数的个数。

sum[i][k]表示用前i个数（第i个数一定会用到），和为k的情况总数。

最后sum[i][m],  0 < i < n，的和就是总的组合数

#include <iostream>
using namespace std;

int main()
{
    int f[10];

    f[0] = 1;
    f[1] = 2;

    for(int i = 2; i < 10; i++)
        f[i] = f[i-1] + f[i-2];

    int sum[10][100];

    int size = 0;

    int N = 13;

    while(size < 10)
    {
        if (f[size] <= N)
            size++;
        else
            break;
    }

    memset(sum, 0, sizeof(sum));

    for(int i = 0; i < size; i++)
    {
        sum[i][f[i]] = 1;
        for(int j = 0; j < i; j++)
            for(int k = 1; k <= N - f[i]; k++)
                sum[i][k + f[i]] += sum[j][k];
    }

    int ret = 0;
    for(int i = 0; i < size; i++)
        ret += sum[i][N];

    cout << ret << endl;
}