狂気を感じる動画として一部で話題になった『フカシギの数え方』 僕も数えてみます! 数え上げ問題なので、まずは定石通りに、問題の状態を数値で表現してみて、それぞれの状態から何通りあるかと考える方針でいきます。 この状態を表現するのに、どのような情報が必要でしょうか。 以下の情報があれば、この状態からゴールまでの通り方の数は一意に決まりそうです。 現在地: (2,2) もう通れない点: (0,0), (1,0), (2,0), (2,1), (1,1), (1,2) ここからの行き先ですが、左と上はもう通っている点なので行けません。 残りは2通りです。 それぞれ、同じように「現在地」と「もう通れない点」から状態を表現できます。 また、この状態だとどうなるでしょう。 すでにゴールに到達してます。 この状態からゴールまでの通り方の数はもちろん1通りです。 以上から、各状態からのゴールまでの通り方は
![『フカシギの数え方』の数え方 - Happy Coder](https://cdn-ak-scissors.b.st-hatena.com/image/square/6f4d783663592fca10452e06824ca7d792d13be8/height=288;version=1;width=512/http%3A%2F%2Ftech.fuqinho.net%2Fwp-content%2Fuploads%2F2012%2F09%2Ffukashigi2.gif)