『フカシギの数え方』の数え方 - Happy Coder

狂気を感じる動画として一部で話題になった『フカシギの数え方』 僕も数えてみます！ 数え上げ問題なので、まずは定石通りに、問題の状態を数値で表現してみて、それぞれの状態から何通りあるかと考える方針でいきます。 この状態を表現するのに、どのような情報が必要でしょうか。 以下の情報があれば、この状態からゴールまでの通り方の数は一意に決まりそうです。 現在地: (2,2) もう通れない点: (0,0), (1,0), (2,0), (2,1), (1,1), (1,2) ここからの行き先ですが、左と上はもう通っている点なので行けません。 残りは２通りです。 それぞれ、同じように「現在地」と「もう通れない点」から状態を表現できます。 また、この状態だとどうなるでしょう。 すでにゴールに到達してます。 この状態からゴールまでの通り方の数はもちろん１通りです。 以上から、各状態からのゴールまでの通り方は