AtCoder Beginner Contest 34 の C を解いた

問題文としては，

のようになります．

こういった問題は，動的計画法の典型的な問題だそうです．後輩の，ヒントマンが言ってました．

事前に計算した内容を元に，今回計算したい内容を求めるみたいなことなのかな？

みたいな感じだと理解しました．

この問題だと，それぞれのマスに行くまでに必要な距離は，

1つ下の点にたどり着く経路の数＋1つ左の点にたどり着く経路の数＝その点に辿り着く経路の数

となるので，それをループでぐんぐん求めていくと解けます．

101 点の，100 点までですが...．

後の 1 点は数学的解法で求めると解けるそうです．

...，はっきり言って，この問題は自力では解けませんでした．このような問題は動的計画法を使うと解ける，ということが思いつけないのです．

どうすれば良いんでしょう...？

幾つか動的計画法な問題を解いてみて，感覚を掴むと良いのかな．