【LeetCode】(70)Climbing Stairs (Easy)

題目

Climbing Stairs

  Total Accepted: 65108  Total Submissions: 189441 My Submissions Question  Solution 

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?

解析

最簡單的思路就是用遞歸，然而這種題目常常遞歸會出錯，超過次數。

直覺的方法就是疊代，其實也很簡單

class Solution {
public:
    int climbStairs(int n) {
       <span style="white-space:pre">		</span>if (n == 1)
		 <span style="white-space:pre">	</span> return 1;
		if (n == 2)
			  return 2;
		  
		  vector<int> stNum(n);
		  stNum[0] = 1;
		  stNum[1] = 2;

		  for (int i = 2; i<n; i++)
		  {
			  stNum[i] = stNum[i-1] + stNum[i-2];
		  }
		  return stNum.back();
    }
};
           

不過還是需要使用一個vector的存儲空間，可以更有效的降低空間。

class Solution {
public:
    int climbStairs(int n) {
       <span style="white-space:pre">		</span>if (n == 1)
			  return 1;
		  if (n == 2)
			  return 2;
  
		  int stNum0 = 1;
		  int stNum1 = 2;
		  int tmp;
		  for (int i = 2;i<n;i++)
		  {
			 tmp = stNum1;
			 stNum1 = stNum0 + stNum1;
			 stNum0 = tmp;
		  }
		  return stNum1;
    }
};
           

大神提供了一個使用數學公式的方法

class Solution {
public:
int climbStairs(int n) {
<span style="white-space:pre">	</span>const double s = sqrt(5);
<span style="white-space:pre">	</span>return floor((pow((1+s)/2, n+1) + pow((1-s)/2, n+1))/s + 0.5);
 }
};