Hedvig Interview - Count of number with no consecutive 1's - 我的博客 - ITeye技术网站

Hedvig Interview - Count of number with no consecutive 1's - 我的博客 - ITeye技术网站
Given integer n, find the number of different binary strings of size n where there are no consecutive 1's.Eg: If n is 2, valid strings are 00, 01, 10. You should return 3.

假设f(n, k)是第n位上为k的数字的个数

无论第n-1位是0还是1，第n位都能取0，故有：
f(n, 0) = f(n-1, 0) + f(n-1, 1)
. 
而只有在第n-1位取0时，第n位才能取1，即：
f(n, 1) = f(n-1, 0)

n位bit能表示的数目总和是：
f(n) = f(n, 0) + f(n, 1) = [f(n-1, 0) + f(n-1, 1)] + f(n-1, 0) = f(n-1) + [f(n-2, 0) + f(n-2, 1)] = f(n-1) + f(n-2)

1. public static int noConsucetive1(int n) {  
2.     if(n <= 0) return 0;  
3.     int[] f = new int[n+1];  
4.     f[0] = 1; f[1] = 2;  
5.     for(int i=2; i<=n; i++) {  
6.         f[i] = f[i-1] + f[i-2];  
7.     }  
8.     return f[n];  
9. }

1. public static int noConsucetive1(int n) {  
2.     if(n <= 0) return 0;  
3.     int[] f1 = new int[n+1];  
4.     int[] f0 = new int[n+1];  
5.     f0[1] = f1[1] = 1;  
6.     for(int i=2; i<=n; i++) {  
7.         f0[i] = f0[i-1] + f1[i-1];  
8.         f1[i] = f0[i-1];  
9.     }  
10.     return f0[n]+f1[n];  
11. }  

Read full article from Hedvig Interview - Count of number with no consecutive 1's - 我的博客 - ITeye技术网站