読者です 読者をやめる 読者になる 読者になる

AtCoder Beginner Contest 34 の C を解いた

問題文としては,

ref : http://abc034.contest.atcoder.jp/tasks/abc034_c

のようになります.

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

動的計画法とは,

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

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

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

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

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

101 点の,100 点までですが....

ref : http://abc034.contest.atcoder.jp/tasks/abc034_c

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

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

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

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