Ruby解题分享--Climbing Stairs

当开始可以发现韩国女团,每个人长得都不一样时,就代表你长大了...

Climbing Stairs

不养羊或兔子之後,开始爬楼梯....

很多语言都会用到斐波那契数,不认识没关系,我们等等用观察法来解。
学程序语言,数学不用好,但学程序後,数学可能会进步...

递回(递归)

wiki

有一天主持人抽奖,喊了:[第5排那位红色衣服的阿宅,你得奖了]。
我刚好是穿红衣也是阿宅,但我不知道我第几排,所以我向我前面的正妹问,请问她是第几排,她也不知道,所以她向他前面比我还肥宅的肥宅问他是第几排,一直问到了第一排。

{我: "不知道", 正妹: "不知道", 比我肥宅: "不知道", 路人一: "不知道", 路人二: "第一排"}

到了第一排的路人二号,终於知道自己是第一排的观众,但他很酷的的回答路人一,我只知道我在第一排。
好险路人二到我没笨到不会加法,於是从路人二开始回头看。

{
 路人二: "我是第一排,那你是我下一位",
 路人一: "前面一,所以我是二,後面的我是二",
 比我肥宅: "前面是二,所以我是三,後面的我是三",
 正妹: "前面是三,所以我是四,後面的我是四",
 我: "前面是四,所以我是五,後面的我是五",
}
#找到自己位置的方法,就是知道前面的人的位置。

以上便是递回最简单的想法。

开始观察

方法只有两种,一步或两步。

#一阶时 method一种
n = 1 
1. 1 step

#二阶时 method二种
n = 2 
#爬法
1. 1 step + 1 step
2. 2 steps

#三阶时 method三种
n = 3
1. 1 step + 1 step + 1 step
2. 2 steps + 1 step
3. 1 step + 2 steps

#四阶时 method五种
n = 4
1. 1 step + 1 step + 1 step + 1 step
2. 2 seep + 1 step + 1 step
3. 1 setp + 2 setp + 1 step
4. 1 step + 1 step + 2 setp
5. 2 setp + 2 setp

# 这边不是观察算式,而是发现到最後方法只有最後一步是1的方法,加上最後一步是2的方法,等於总方法数。
# 最後一步是1时 == n - 1 , 最後一步是2时 == n - 2。
# 另外整理答案 hash = {"1": 1, "2": 2, "3": 3, "4": 5}
hash[1] = 1 
hash[2] = 2
hash[3] = 4 
hash[4] = 5 #从三四阶时开始符合 n = (n - 1) + (n - 2)
# 养动物达人公式就出现了 f(x) = f(x-1) + f(x-2)

解答

def climb_stairs(n)
  methods = {}
  methods[1] = 1
  methods[2] = 2
  3.upto(n) do |n|
    methods[n] = methods[n - 2] + methods[n - 1]
  end
  methods[n]
end

另外可用default_proc = -> 语法

def climb_stairs(n)
    fibona_hash = { 0 => 0, 1 => 1, 2 => 2, 3 => 3 }  
    fibona_hash.default_proc = ->(hash, n) {hash[n] = hash[n-1] + hash[n-2]} 
    fibona_hash[n]
end
# "->", lambda。
# 嗯,我没分享过block,proc及lambda....

请先看https://ruby-doc.org/core-3.0.2/Hash.html#method-i-default_proc

再进化一点...

def climb_stairs(n)
  return 0 if n == 0
  a, b = 0, 1
  n.times { a, b = b, b + a }
  b
end

补充:

2.7.3 :013 > arr = [1, 2, 3]
 => [1, 2, 3] 
2.7.3 :014 > arr[0] = arr[1]
 => 2 
2.7.3 :015 > arr
 => [2, 2, 3] 
2.7.3 :016 > arr = [1, 2, 3]
 => [1, 2, 3] 
2.7.3 :017 > arr[0] ,arr[1] = arr[1], arr[0]
 => [2, 1] 
2.7.3 :018 > arr
 => [2, 1, 3] 

虽然就是费波纳,但是观察爬楼梯爬高点就会发现了。