2019-赤ずきんちゃんの花壇-解説
- 考案国：ルーマニア
- 正解
- 説明
- それぞれの花壇に対して、赤ずきんが左上から集められる花の最大数を求めることができます。計算は次のように行います。
- その花壇がひとつ前の1個の花壇だけから到達できるとき、その花壇の最大値は「その花壇の花の数と、ひとつ前の花壇の最大値の合計」です。
- その花壇がひとつ前の2個の花壇から到達できるとき、その花壇の最大値は「その花壇の花の数と、ひとつ前の花壇の最大値の大きい方の合計」です。
- それぞれの花壇に対して、赤ずきんが左上から集められる花の最大数を求めることができます。計算は次のように行います。
- 実際のコンピュータでは
- この問題では、最適な値を求めるために、動的計画法と呼ばれる戦略を使っています。動的計画法では、複数の中間的な計算結果を記録しておいて利用します。
- 今回の例では、それぞれの花壇に最大値を計算して記録しておくことが相当します。その計算をスタートに近い花壇から徐々に進めていくことで、少しずつ花壇への最大値の計算結果が広がり、やがてゴールの花壇まで到達すると目的の最終結果を得られます。
注があるものを除き, このサイトの内容物は
