《Cracking the Coding Interview》——第9章：递归和动态规划—

《Cracking the Coding Interview》——第9章：递归和动态规划——题目1

2014-03-20 02:55

题目：小朋友跳台阶，每次跳1层或2层，那么跳N层总共有多少种跳法。

解法：斐波那契数列。

代码：

 1 // 9.1 A child can run up the stair with n staircases. Every time he can hop up by 1, 2 or 3 steps. How many possible way to do this are there?
 2 #include <cstdio>
 3 #include <vector>
 4 using namespace std;
 5 
 6 int main()
 7 {
 8     int n;
 9     int i;
10     vector<int> v;
11     
12     v.push_back(1);
13     n = 1;
14     while (true) {
15         i = v[n - 1];
16         if (n >= 2) {
17             i += v[n - 2];
18         }
19         if (n >= 3) {
20             i += v[n - 3];
21         }
22         if (i >= 1000000000) {
23             break;
24         } else {
25             v.push_back(i);
26         }
27         ++n;
28     }
29     printf("n = %d
", (int)v.size());
30     
31     while (scanf("%d", &n) == 1 && n > 0 && n < (int)v.size()) {
32         printf("%d
", v[n]);
33     }
34     v.clear();
35     
36     return 0;
37 }