同じところを二度通らない組み合わせ

『フカシギの数え方』 おねえさんといっしょ！ みんなで数えてみよう！

最短経路なら二項定理で求まるのだが、最短経路ではないので意外と難しい。DP(動的計画法)で求まると思うが一筋縄ではいかない。
上の動画は、DPで解くアルゴリズムを解説するのかと思いきや、マジキチな結末が待っている。なかなかシュールだ。是非最後まで見て欲しい。