LeetCode Climbing Stairs階段を登る

再帰法(TLEコード):

 1 class Solution {

 2 public:

 3     int climbStairs(int n) {

 4         if(n==0)

 5             return 1;

 6         if(n<0)

 7             return 0;

 8         return (climbStairs(n-1)+climbStairs(n-2));

 9     }

10 };

 
ダイナミックプランニング:

 1 class Solution {

 2 public:

 3     int climbStairs(int n) {

 4         if(n==1) return 1;

 5         if(n==2) return 2;

 6         int a=1,b=2,c=0,i;

 7         for( i=0;i<n-2 ;i++ ){

 8             c=a+b;

 9             a=b;

10             b=c;

11         }

12         return c;

13     }

14 };

 
标题:階段を登って、1本の階段の階数を与えて、毎回1歩、あるいは2歩一緒に歩くことができて、それでは2つの歩き方がこのn階を歩き終えることができます.この階段を何種類歩けばいいか聞いて、戻ります.
考え方:n=1の場合、1を返す.n=2の場合、2を返します.n>3の場合、n−1およびn−2の返される数が返される.たとえばn=3であれば,1+2の値を返し,n=4で3+2を返す.類推する.
ツッコミ:この問題に困惑していたのか、再帰で書いてみたら、だめだった.コードは簡単だったが.それからいろいろな方法を考えて、この再帰法でそれぞれの戻り値を計算して、法則を見つけました.なるほど.~