LeetCode) 70. Climbing Stairs

1300 ワード
Java leetcode 2021 テキストリンク

階段を上る時の数の問題を求めます.

Language: java

class Solution {
    public int climbStairs(int n) {
        int sum = 0;
        
        if(n == 1) return 1;
        if(n == 2) return 2;
        
        sum = climbStairs(n-2) + climbStairs(n-1);
        return sum;
    }
}
書き終わったら分かりますが、結果はフィボナッチの問題です.
アルゴリズムの問題を解く理由を知っています...
しかし問題が発生しました
最後に45個の透かしを入れると、TimeLimit Exceededエラーが発生します.
理由はなんだろう…?
しかし、グーグルを遊んでいたとき、私のような問題が発生した人は1人や2人ではないことに気づいた.
だから見つけた解決策は配列を指定することです.
class Solution {
    int[] stairs = new int[46];
     
    public int climbStairs(int n) {
        
        stairs[1] = 1;
        stairs[2] = 2;
        
        for(int i = 3; i < stairs.length; i++) {
            stairs[i] = stairs[i-1] + stairs[i-2];
        }
        
        return stairs[n];
    }
}
上記の疑問を解消することができます.
無計画にsumで回ると、また回るたびにもう一度作って探しに行くので時間がかかります.
nの値も
45まで指定するので、45の大きさの配列を作っておき、nに対応する値を入れておき、戻るときにその値を外せばいいのです!
時間もずいぶん短くなり、いい方法のようです.
はあ、まったく関係ないように見える問題で、フィボナッチだったのか!知りたければ、いったいどのくらいかかるのか、いろいろな問題を解決してみようか・・・反省+感嘆中
[TIL] Modern JavaScript
[アルゴリズム/Programmers]文字列基本