LeetCode——Climbing Stairs
918 ワード
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?
原題リンク:https://oj.leetcode.com/problems/climbing-stairs/
階段を登っています.上部に着くにはnステップが必要です.
1歩か2歩登るたびに.何種類の独立した頂上まで登る方法がありますか?
考え方:まず再帰的な解法を簡単に思いついた.でもタイムアウト.
だから非再帰的な方式を採用して、実はこの問題はフィボナッチの数列の和を求めるのと似ていますが、再帰は遅いだけでなく溢れ出す可能性があります.次に、preが前のn−1ステップの方法数を表し、currentが第nステップの方法数を表す非再帰的な方法を採用する.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
原題リンク:https://oj.leetcode.com/problems/climbing-stairs/
階段を登っています.上部に着くにはnステップが必要です.
1歩か2歩登るたびに.何種類の独立した頂上まで登る方法がありますか?
考え方:まず再帰的な解法を簡単に思いついた.でもタイムアウト.
public int climbStairs(int n) {
if(n < 0)
return 0;
if(n <= 1)
return 1;
return climbStairs(n - 1) + climbStairs(n - 2);
}
だから非再帰的な方式を採用して、実はこの問題はフィボナッチの数列の和を求めるのと似ていますが、再帰は遅いだけでなく溢れ出す可能性があります.次に、preが前のn−1ステップの方法数を表し、currentが第nステップの方法数を表す非再帰的な方法を採用する.
public int climbStairs(int n) {
if (n == 0 || n == 1)
return 1;
int pre = 1;
int current = 1;
for (int i = 2; i <= n; i++) {
int temp = current + pre;
pre = current;
current = temp;
}
return current;
}