フィボナッチ数列を使用した方法
1段登る場合と、2段登る場合で再帰的に計算する方法です。
class Solution {
public:
int climbStairs(int n) {
return n <= 2
? n
: climbStairs(n-1) + climbStairs(n-2);
}
};ただし、指数時間 の計算になってしまうためタイムアウトになってしまいます。
メモ化を使用する
class Solution {
private:
static std::unordered_map<int, int> cash_;
public:
int climbStairs(int n) {
if (cash_.count(n) == 1) {
return cash_.at(n);
}
cash_.emplace(n, climbStairs(n-1) + climbStairs(n-2));
return cash_.at(n);
}
};
std::unordered_map<int, int> Solution::cash_ = {
{ 1, 1 },
{ 2, 2 },
};メモ(キャッシュ)を静的メンバとしていますが、ただのメンバでも十分だと思います。
インスタンスの破棄が何度もされる場合は静的メンバの方が計算効率が良いかと思いますが、一度計算するとその後一生メモリを食うので非機能要件との兼ね合い次第といったところでしょうか。
以上です！