[LeetCode] 70 Climbing Stairs

4664 ワード
アルゴリズム#アルゴリズム# Java leetcode テキストリンク
Description
You are climbing a staircase. It takes n steps to reach the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Example 1:
Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
Example 2:
Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step
Constraints:
  • 1 <= n <= 45
    • に答える

  • 階段は一度に1つか2つ登ることができ、階段を登る方法を求める問題です.

  • DPで解きます.
    階段が1つあれば、階段を登る方法は1つ(1格)です.
    2つの階段があれば、階段を登る方法は2つ(1格1格2格)です.
    3つ以上の階段があったら、
    階段を登る方法数=現在の階段-1に登る方法数+現在の階段-2に登る方法数
    いいですよ.
    F(n)=F(n-1)+F(n-2)=>フィボナッチ数列

  • 1つか2つの階段があれば、階段の数字を返してください.
    3つ以上の階段があったら、

  • この場合,再帰関数を用いずにbottom−up方式で問題を解決できる.

  • 時間的複雑さは,forゲートがnを1回回るのでO(N)である.
    空間複雑度は,各ステップの値を格納するためのO(N)配列であるが,現在のステップアップに必要な値は前の2つのステップのみであり,最終的にはO(1)である.
    • コード#コード#
    class Solution {
    public int climbStairs(int n) {
        int[] sumArr = new int[n + 1];

        if (n == 1 || n == 2) {
            return n;
        } else {
            sumArr[0] = 0;
            sumArr[1] = 1;
            sumArr[2] = 2;

            for (int i = 3; i <= n; i++) {
                sumArr[i] = sumArr[i - 1] + sumArr[i - 2];
            }
        }
        return sumArr[n];
    }
}
    Android UiAutomator自動化テスト時にログファイルを保存する方法
    MongoDBの簡単な使い方