【九度】题目1388：跳台阶 【LeetCode】Climbing Stairs

本文主要是介绍【九度】题目1388：跳台阶 【LeetCode】Climbing Stairs，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1、【九度】题目1388：跳台阶
时间限制：1 秒内存限制：32 兆特殊判题：否提交：2435解决：995
题目描述：
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
输入：
输入可能包含多个测试样例，对于每个测试案例，
输入包括一个整数n(1<=n<=70)。
输出：
对应每个测试案例，
输出该青蛙跳上一个n级的台阶总共有多少种跳法。
样例输入：
5
样例输出：
8
答疑：
解题遇到问题?分享解题心得?讨论本题请访问： http://t.jobdu.com/thread-8111-1-1.html
【解题思路】
以下这个解释参考别人写好的。（地址： http://t.jobdu.com/thread-8111-1-1.html，name：acaiwlj）
*1.当n = 1时，只有一种跳法，s = 1;
*2.当n = 2时，有两种跳法, s = 2;
*3.当n > 2时，有两种分解方法：
*  (1)当第一下跳一个台阶时，s(n) = s(n-1);
*  (2)当第一下条一个台阶时，s(n) = s(n-2);
*因此可以得到递归表达式：
*s(n) = 1, n = 1;
*s(n) = 2, n = 2;
*s(n) = s(n-1) + s(n-1), n > 2;
注意：可以用数组，以空间换时间，也可以用递归，但是递归太慢，会导致很多重复计算。本题采用数组。
其实结果就是斐波那契序列，结果用long，int会溢出。

Java AC

import java.io.StreamTokenizer;public class Main {/** 1388*/public static void main(String[] args) throws Exception {StreamTokenizer st = new StreamTokenizer(System.in);long array[] = new long[80];array[0] = 1;array[1] = 2;for (int i = 2; i < array.length; i++) {array[i] = array[i-1] + array[i-2];}while (st.nextToken() != StreamTokenizer.TT_EOF) {int n = (int) st.nval;System.out.println(array[n-1]);}}
}
/**************************************************************Problem: 1388User: wzqwsrfLanguage: JavaResult: AcceptedTime:70 msMemory:14532 kb
****************************************************************/

C++ AC

#include <stdio.h>
const int maxn = 72;
long array[maxn];
int n;
int main(){while(scanf("%d",&n) != EOF){if(n == 1){printf("1\n");continue;}array[1] = 1;array[2] = 2;for(int i = 3; i < n + 1; i++){array[i] = array[i-1] + array[i-2];}printf("%ld\n", array[n]);}return 0;
}/**************************************************************Problem: 1388User: wangzhenqingLanguage: C++Result: AcceptedTime:0 msMemory:1020 kb
****************************************************************/

2、【LeetCode】Climbing Stairs
Total Accepted: 17976 Total Submissions: 53883 My Submissions
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?
Have you been asked this question in an interview? 

Java AC 336ms

public class Solution {public int climbStairs(int n) {if (n == 1) {return 1;}int array[] = new int[n+1];array[1] = 1;array[2] = 2;for(int i = 3; i < n+1; i++){array[i] = array[i-1] + array[i-2];}return array[n];}
}

Python AC 120ms

class Solution:# @param n, an integer# @return an integerdef climbStairs(self, n):if n == 1:return 1array = [0 for i in range(n+1)]array[1] = 1array[2] = 2for i in range(3, n+1):array[i] = array[i-1] + array[i-2]return array[n]

这篇关于【九度】题目1388：跳台阶 【LeetCode】Climbing Stairs的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---