2016.6.21——Climbing Stairs

Climbing Stairs

本题收获：

1.斐波那契函数f(n) = f(n-1) + f(n -2)

　　题目：　

　　You are climbing a stair case. It takes n steps to reach to the top.

　　Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

　　有n阶台阶，每次可以走2步或者1步，问有多少种方法到达顶端

　　思路：

　　　　leetcode:是个斐波那契函数的迭代

　　　　　　对于第n阶来说，有两种方法，从n-1 走 1阶到n，从n-2走2阶到n（刚开始想从n-2处到n 可以走1次2步和 2次 1步，但是走1次一步不就成了n-1到n了, 重复）

　　代码：

 class MyClass

 {

 public:

     int clambingStairs(int n)

     {

         if (n == ) return ;

         if (n == ) return ;

         if (n == ) return ;

         int f2 = , f1 = , f = ;

         for (int i = ; i < n; i++)

         {

             f = f1 + f2;                //f2可以看做f(n-2)

             f2 = f1;                    //f1看做f(n-1)

             f1 = f;                        //f看做f(n)

         }

         return f;

     }

 };

　　我的测试代码：

 // Climbing Stairs.cpp : 定义控制台应用程序的入口点。

 //

 #include "stdafx.h"

 #include "iostream"

 using namespace std;

 class MyClass

 {

 public:

     int clambingStairs(int n)

     {

         if (n == ) return ;

         if (n == ) return ;

         if (n == ) return ;

         int f2 = , f1 = , f = ;

         for (int i = ; i < n; i++)

         {

             f = f1 + f2;                //f2可以看做f(n-2)

             f2 = f1;                    //f1看做f(n-1)

             f1 = f;                        //f看做f(n)

         }

         return f;

     }

 };

 int _tmain(int argc, _TCHAR* argv[])

 {

     int n = ;

     cin >> n;

     MyClass solution;

     int m = ;

     m = solution.clambingStairs(n);

     cout << m << endl;

     system("pause");

     return ;

 }

巴特西

2016.6.21——Climbing Stairs

Climbing Stairs

最新文章

热门文章