[CareerCup][Google Interview] 打印所有的Binary Number - chkkch - 博客园
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,的和就是总的组合数
Read full article from [CareerCup][Google Interview] 打印所有的Binary Number - chkkch - 博客园