Climping Stairs lintcode/leetcode

青旅半醒 2022-07-16 11:07 82阅读 0赞

### 转自： [http://blog.csdn.net/jfkidear/article/details/41989337][http_blog.csdn.net_jfkidear_article_details_41989337]    ###

### `public int climbStairs(int n) { // write your code here if( n== 0)return 1; if (n < 3) return n; int n1 = 1; int n2 = 2; for (int i = 3; i <= n; i+=2) { n1 = n1 + n2; n2 = n1 + n2;//二步长求斐波那契 } if (n%2 == 1)return n1; return n2;`  `}`         ###

### 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?

简单题目，相当于fibonacci数列问题，难点就是要会思维转换，转换成为递归求解问题，多训练就可以了。

所以这种类型的题目相对于没有形成递归逻辑思维的人来说，应该算是难题。

我的想法是：

每次有两种选择，两种选择之后又是各有两种选择，如此循环，正好是递归求解的问题。

写成递归程序其实非常简单，三个语句就可以：

**\[cpp\]** [view plain][] [copy][view plain] [![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

1.  **int** climbStairsRecur(**int** n) \{ 
2.  **if** (n == 1) **return** 1; 
3.  **if** (n == 2) **return** 2; 
4.  **return** climbStairsRecur(n-1) + climbStairsRecur(n-2); 
5.   \}

但是递归程序一般都是太慢了，因为像Fibonacci问题一样，重复计算了很多分支，我们使用动态规划法填表，提高效率，程序也很简单，如下：

**\[cpp\]** [view plain][] [copy][view plain] [![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

1.  **int** climbStairs(**int** n) 
2.   \{ 
3.   vector<**int**> res(n+1); 
4.   res\[0\] = 1; 
5.   res\[1\] = 1; 
6.  **for** (**int** i = 2; i <= n; i++) 
7.   \{ 
8.   res\[i\] = res\[i-1\] + res\[i-2\]; 
9.   \} 
10. **return** res\[n\]; 
11.  \}

动态规划法用熟了，高手就需要节省空间了，如下：

**\[cpp\]** [view plain][] [copy][view plain] [![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

1.  **int** climbStairs2(**int** n) 
2.   \{ 
3.   vector<**int**> res(3); 
4.   res\[0\] = 1; 
5.   res\[1\] = 1; 
6.  **for** (**int** i = 2; i <= n; i++) 
7.   \{ 
8.   res\[i%3\] = res\[(i-1)%3\] + res\[(i-2)%3\]; 
9.   \} 
10. **return** res\[n%3\]; 
11.  \}

当然，不使用上面的数组也是可以的，直接使用三个变量保存结果也是一样的。

**\[cpp\]** [view plain][] [copy][view plain] [![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

1.  //2014-2-10 update
2.  **int** climbStairs(**int** n) 
3.   \{ 
4.  **if** (n < 4) **return** n; 
5.  **int** a = 2, b = 3, c = 5; 
6.  **for** (**int** i = 5; i <= n; i++) 
7.   \{ 
8.   a = c; 
9.   c = b+c; 
10.  b = a; 
11.  \} 
12. **return** c;

[http_blog.csdn.net_jfkidear_article_details_41989337]: http://blog.csdn.net/jfkidear/article/details/41989337
[view plain]: http://blog.csdn.net/kenden23/article/details/17377869#
[CODE]: https://code.csdn.net/assets/CODE_ico.png
[CODE_CODE]: https://code.csdn.net/snippets/121779
[ico_fork.svg]: https://code.csdn.net/assets/ico_fork.svg
[ico_fork.svg 1]: https://code.csdn.net/snippets/121779/fork