【Paiza】2項間漸化式 1【レベルアップ問題集】 - Qiita

はじめに IT／WEBエンジニアに特化した転職・就職・学習サイト「paiza（パイザ）」のレベルアップ問題集から１問ピックアップして、とことん噛み砕いた解説を備忘録としてまとめました。 今回は「DPメニュー」から「2項間漸化式 1」を解説していきます。 問題 整数 x, d, k が与えられます。 次のように定められた数列の k 項目の値を出力してください。 a_1 = x a_n = a_{n-1} + d (n ≧ 2) 解説 動的計画法では、 部分問題 に分ける DPテーブル を作成する ことが重要です。 部分問題に分ける 部分問題 について考える際は、「最後から」手順を追っていくことがポイントとなります。今回の問題では k 項目の値、すなわち a_k を得ることが目的です。ここで、与えられた数列の式から a_k は a_{k-1} + d で表されることが分かります。次に a_{k