【九度】テーマ1388:階段を跳ぶ&&【LeetCode】Climbing Stairs

1、【九度】題1388:ステップジャンプ時間制限:1秒メモリ制限:32メガ特殊判題:No提出:2435解決:995
タイトルの説明:
1匹のカエルは一度に1段の階段を飛び上がることも、2段を飛び上がることもできます.このカエルが1つの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の場合、ジャンプ法は1つしかありません.s=1です.
*2.n=2の場合、2つのジャンプ法があり、s=2である.
*3.n>2の場合、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: 1388
    User: wzqwsrf
    Language: Java
    Result: Accepted
    Time:70 ms
    Memory: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
");
            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
", array[n]);
    }
    return 0;
}
 
/**************************************************************
    Problem: 1388
    User: wangzhenqing
    Language: C++
    Result: Accepted
    Time:0 ms
    Memory: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 integer
    def climbStairs(self, n):
        if n == 1:
            return 1
        array = [0 for i in range(n+1)]
        array[1] = 1
        array[2] = 2
        for i in range(3, n+1):
            array[i] = array[i-1] + array[i-2]
        return array[n]