Climbing Stairs

来源：Leetcode

原帖：http://oj.leetcode.com/problems/climbing-stairs/

题目：
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?
Solution: Climd one step from last stair or climb 2 steps from the last last stair.
Fibnacacci number.

代码：

 class Solution {  
 public:  
   int climbStairs(int n) {  
     int last = 1;  
     int lastlast = 1;  
     for (int i = 2; i <= n; i++) {  
       int step = last + lastlast;  
       lastlast = last;  
       last = step;  
     }  
     return last;  
   }  
 };  
   
 // {{1,1}, {1,0}} ^ n = {{f(n), f(n-1)}, {f(n-1), f(n-2)}};  
 class Solution {  
 public:  
   void multiply(int a[2][2], int b[2][2]) {  
     int c[2][2] = {0};  
     for (int i = 0; i < 2; ++i) {  
       for (int j = 0; j < 2; ++j) {  
         for (int k = 0; k < 2; ++k) {  
           c[i][j] += a[i][k] * b[k][j];  
         }  
       }  
     }  
     for (int i = 0; i < 2; ++i) {  
       for (int j = 0; j < 2; ++j) {  
         a[i][j] = c[i][j];  
       }  
     }  
   
   }  
   
   void power(int a[2][2], int n) {  
     if (n <= 1) return;  
     int c[2][2] = {{1,1}, {1,0}};  
     power(a, n/2);  
     multiply(a,a);  
     if (n % 2 == 0) return;  
     multiply(a, c);  
   }  
   
   int climbStairs(int n) {  
     if (n == 1) return 1;  
     int matrix[2][2] = {{1, 1}, {1, 0}};  
     power(matrix, n);  
     return matrix[0][0];  
   }  
 };