LeetCode - 70. Climbing Stairs

# [70. Climbing Stairs](https://leetcode.com/problems/climbing-stairs/)

普通に一歩目は一段または二段、二歩目も一段または二段ってやると、`O(2^N)` になってしまい、[死ぬ](https://www.bigocheatsheet.com/)

# Ver. 1
 
最初に書いたやつ。我ながら雑なコード。

計算量を大きくしないように

- 合計が`N`段になるような`1`段と`2`段の回数の組み合わせを見つける `x + 2*y == n`
- その組み合わせに対して順列を数える `ary.permutation.uniq.size`

とやってみた

```ruby

# @param {Integer} n
# @return {Integer}
def climb_stairs(n)
  distinct_ways = 0

  x = 0 
  while x <= n
    y = 0 
    while y <= n
      if x + 2*y == n
        ary = []
        x.times{|x| ary << 1}  
        y.times{|y| ary << 2}
        distinct_ways =  distinct_ways + ary.permutation.uniq.size
      end
      y = y + 1
    end
    x = x + 1
  end
    
  distinct_ways
end
```

# スコア

```
Time Limit Exceeded
```

うむ。

# ベンチマーク

遅い子はどこだー？ベンチマークを挟みます。

```ruby

# @param {Integer} n
# @return {Integer}
require 'benchmark'

def climb_stairs(n)
  distinct_ways = 0

  x = 0 
  while x <= n
    y = 0 
    while y <= n
      if x + 2*y == n

### ベンチマーク
Benchmark.bm 30 do |r|

        ary = []

  r.report "create combination(array)" do # (計測したい処理その1)
        x.times{|x| ary << 1} 
        y.times{|y| ary << 2}
  end

  r.report "permutation from combination" do
    distinct_ways =  distinct_ways + ary.permutation.uniq.size # (計測したい処理その2)
  end

end
###

      end
      y = y + 1
    end
    x = x + 1
  end
  distinct_ways
end

climb_stairs(10)
```

ベンチマーク結果

```
                                     user     system      total        real
create combination(array)        0.000000   0.000000   0.000000 (  0.000009)
permutation from combination     0.000000   0.000000   0.000000 (  0.000549)
                                     user     system      total        real
create combination(array)        0.000000   0.000000   0.000000 (  0.000004)
permutation from combination     0.000000   0.000000   0.000000 (  0.002103)
                                     user     system      total        real
create combination(array)        0.000000   0.000000   0.000000 (  0.000006)
permutation from combination     0.020000   0.000000   0.020000 (  0.013463)
                                     user     system      total        real
create combination(array)        0.000000   0.000000   0.000000 (  0.000010)
permutation from combination     0.130000   0.000000   0.130000 (  0.133766)
                                     user     system      total        real
create combination(array)        0.000000   0.000000   0.000000 (  0.000004)
permutation from combination     1.260000   0.010000   1.270000 (  1.281589)
                                     user     system      total        real
create combination(array)        0.000000   0.000000   0.000000 (  0.000004)
permutation from combination    13.800000   0.100000  13.900000 ( 14.074233)
```

`N`が`10`で`13秒`だから... 激遅いな。`permutation` が遅い。全パターン作ってるみたい。例えば`[1,2,2,1,1,1,1,1]` というパターンだったとしたら、この`1` を全部別モンとカウントするので `40320`通り作ってしまう。

```ruby

[13] pry(main)> [1,2,2,1,1,1,1,1].permutation.size                                                                                
=> 40320
```

本当は`10!/(6!*2!)`の`28`通りでいいはず。


# Ver. 2

自分で同じ値があることを考慮した`permutation` ならぬ `prem` を書いた。`group_by(&:itself)` が裏技的ですいません

```ruby
# @param {Integer} n
# @return {Integer}

def factorial(m)
  (1..m).inject(1,:*)
end

def prem(ary)
  h = ary.group_by(&:itself)
  h[1] = [1] if !h.has_key?(1)
  h[2] = [2] if !h.has_key?(2)
  factorial(ary.size)/(factorial(h[1].size)*factorial(h[2].size))
end

def climb_stairs(n)
  distinct_ways = 0
  x = 0
  while x <= n
    y = 0
    while y <= n
      if x + 2*y ==n
        ary = []
        x.times{|x| ary << 1}
        y.times{|y| ary << 2}
        distinct_ways =  distinct_ways + prem(ary)
      end
      y = y + 1
    end
    x = x + 1
  end
  distinct_ways
end
```

# スコア

```yaml

Runtime: 40 ms, faster than 21.78% of Ruby online submissions for Climbing Stairs.
Memory Usage: 9.4 MB, less than 100.00% of Ruby online submissions for Climbing Stairs.
```

まあ、あまりよくないが、こんなもんかな...

# 参考
- [\[ruby\]\[メモ\] 階乗](https://qiita.com/rtoya/items/6d248b0817acd399603b)
- [Ruby でベンチマークを取る方法](https://qiita.com/scivola/items/c5b2aeaf7d67a9ef310a)