asaのブログ

プログラミングの勉強まとめ

ALDS1_10_A フィボナッチ数列と動的計画法

 研究でナップザック問題が出てきたので、久しぶりにアルゴリズム問題を解いています。使用している参考書は下の本です。

  例のごとく、この参考書はCとC++で解答が書かれていますので、Javaで解いた解答を載せておきます。

 

 コード

 最初に素朴に解いたものです。フィボナッチ数列を計算するメソッドを書いてそれを再帰的に呼び出しています。ただ、これだとすでに一度計算した分の項も再度計算することになり時間がすごくかかります。AIZU ONLINE JUDGE通りません。

gistb9d7efc948c35cf808a5ebd03175afae

 そこで、一度計算した値を配列に保管しておき、再計算しなくていいようにコードを書き直します。メモリの使用が大きくなりますが計算時間は遥かに短くて済みます。

gistc1097f1cc58ba934282c622bad67abd1

 クラス名をMainに変えて、余分な文字を消すとそのままJUDGEが通りました。