定番アルゴリズム「DP（動的計画法）」をプログラミング練習問題集で学ぼう！

f:id:paiza:20210311135032j:plain
f:id:paiza:20210318110540p:plain こんにちは。paizaラーニングでコンテンツ制作をしている学生スタッフの工藤です。

みなさん、「DP（Dynamic Programming、動的計画法）」って知っていますか？

DPは代表的なアルゴリズムのひとつで、競技プログラミングの問題を解く際にも多く用いられます。そのため耳にしたことはあるかもしれませんが、慣れるまでは扱いが難しく実用性が分からないという方も多いと思います。

ただし、ある程度問題を解いていくとパターンのようなものが見えてくるはずなので、たくさん問題に触れてみるのがおすすめです。

そこで今回は、paizaラーニングのレベルアップ問題集に追加された「DPメニュー」を使って、DPの問題に慣れるための学習法を紹介していきます！

DP（動的計画法）とは

本題の問題集の紹介に入る前に、DPとはどんなアルゴリズムなのか簡単にご紹介します。

こういうときはひとまずWikipediaを見てみましょう。DPとはなにものかについてこう書かれています。

対象となる問題を複数の部分問題に分割し、部分問題の計算結果を記録しながら解いていく手法を総称してこう呼ぶ。
（出典）動的計画法 - Wikipedia

分かるような分からないような……。もう少し見てみると、DPは以下の2つの条件を満たす必要があるようです。

帰納的な関係の利用：いくつかの小さな単位に分割した問題の計算結果を大きな問題を解くために利用する。
計算結果の記録：小さな単位に分割した問題の計算結果を表に記録し、そこから参照することで何度も同じ計算をおこなうことを避ける。

具体例については、のちほど練習問題集で見ていきましょう。

なお、こちらのサイトがもう少し噛み砕いて解説してくださっているので、興味がある方は参照してみてください。

（参考）うさぎでもわかるアルゴリズム　動的計画法

レベルアップ問題集とは

「DPメニュー」は、レベルアップ問題集にて公開しています。

レベルアップ問題集とは、プログラミング学習における計算ドリルや漢字ドリルのようなものだと思ってください。

ドリルのようにプログラミング問題を解き進めながら、解答例となるコード（一部言語）や解説文も参照できる*1ため分からないことを理解したり、苦手なポイントを克服したりできるように作られています。

paizaが提供しているスキルチェックとは異なり時間制限がなく、問題文や自分の解答コードを公開することが認められていますので、誰かと協力して取り組むことも可能です。

練習問題集「DPメニュー」

今回追加されたDPメニューでは、その名の通り、動的計画法（Dynamic Programming）について学習することができます。

DPメニューは、DPを知らない方や、DPは知っているけれど自力で状態の遷移を導き出すことが難しい方に取り組んでいただくことを想定して作成しています。

前提として、標準入出力や配列、if文やfor文などの基礎的な文法についてはひと通り理解している必要があります。

標準入力については、言語別で学習講座を公開していますのでこちらの一覧から取り組みたい言語を選択して受講してみてください。合わせてレベルアップ問題集の「標準入力メニュー」「標準出力メニュー」も解いておくとよいでしょう。

基礎文法が理解できているかどうかは、同じく問題集の「配列メニュー」「条件分岐メニュー」を解いて確認してみてください。

出題される問題の特徴

DPメニューにはプログラミング問題が全21問用意されています。

問題集は6つのセクションに分かれており、各セクションは、1つの「ボス問題」といくつかの「準備問題」によって構成されています。最初の「準備問題」ではそのセクションで扱うテーマについて、ていねいに導入をおこなっており、「準備問題」を順に解いていくことで最後の「ボス問題」が自力で解けるように構成されています。

なお、現在Python3とC++の解答コード例を用意しています。

1：漸化式

1つめのセクションは「漸化式」です。

漸化式とは、数学において各項がそれ以前の項の関数として定まるという意味で数列を再帰的に定める等式のことを言います。（出典：漸化式 - Wikipedia
）DPの問題を解く際に大前提となりますので、思い出しておきましょう。

このセクションでは、さまざまな種類の漸化式の問題を通して、DPがどういった思想・考察に基づいたアルゴリズムなのか、DPの問題にどのようにアプローチするとよいのかを学ぶことができます。

最初の問題がDPの入門のような感じで、少しずつ難易度が上がっていくように構成されているため、DPが分からない人でも無理なく取り組めるようになっています。

最初の1問を軽く見ておきましょう。DPの説明とヒント（参考となる擬似コードつき）も記載されています。

2項間漸化式 1 (paizaランク C 相当)

はじめに：

このメニューでは、動的計画法 (Dynamic Programming, 以下 DP と表記します) について扱います。
DP は、一言でいうと「問題を部分問題に分割し、部分問題の答えを記録しながら、それらを利用することによって元の問題の答えを得る手法」です。
問題をどのように分割するか、部分問題の答えをどのように利用するかなどは問題により異なります。このメニューを通してさまざまなDPの問題に触れ、そのノウハウを身につけていきましょう。
まずは、早速問題を見てみましょう。

問題：

整数 x, d, k が与えられます。
次のように定められた数列の k 項目の値を出力してください。

a_1 = x

a_n = a_{n-1} + d (n ≧ 2)

入力される値：

x d k

期待する出力：

数列の k 項目の値を出力してください。
また、末尾に改行を入れ、余計な文字、空行を含んではいけません。
a_k

条件：

すべてのテストケースにおいて、以下の条件をみたします。

-1,000 ≦ x ≦ 1,000

-1,000 ≦ d ≦ 1,000

1 ≦ k ≦ 1,000

提出結果画面では、各テストケースの入力値および解説（解法のポイント）を見ることができますので、正解できなかった場合でもそれらを参考に理解を深めていただければと思います。

2：階段ののぼり方の通り数

2つめのセクションは「階段ののぼり方の通り数」です。このセクションでは、DPの定番である以下のような問題を扱っています。

整数 n が与えられます。
階段をのぼるのに、1歩で1段または2段をのぼることができるとき、n 段の階段をのぼる方法は何通りあるでしょうか。

1歩でのぼることができる段数が変化した場合や、上り方が3種類以上に増えた場合など、さまざまなバリエーションの問題を用意しています。

3：最安値を達成する組合せ

3つめのセクションは「最安値を達成する組合せ」です。このセクションでは、以下のような問題を扱っています。

八百屋にて、りんご1個が a 円、りんご2個が b 円で売られています。
りんごの買い方を工夫したとき、n 個のりんごを手に入れるために必要な金額の最小値はいくらでしょうか。

りんごの個数が変化した場合や、りんごの売られ方が変化した場合など、さまざまなバリエーションの問題を用意しています。

4：数列の最長連続部分列

4つめのセクションは「数列の最長連続部分列」です。このセクションでは、以下のような問題を扱っています。

n 人が横一列に並んでいます。左から i 番目の人を人 i と呼ぶことにします。人 i の身長は a_i [cm]です。
人 l ,人 l+1, ... , 人 r からなる区間 [l, r] について、すべての l ≦ i < r に対して a_i ≦ a_{i+1} が成り立っているとき、区間 [l, r] は背の順であると呼ぶことにします。また、区間 [l, r] の長さを r-l+1 とします。
背の順であるような区間のうち、最長であるものの長さを出力してください。

少々複雑になってきましたが、問題文をしっかり読んで順にこなしていけば大丈夫です！ぜひじっくり取り組んでみてください。

5：数列の最長部分列

5つめのセクションは「数列の最長部分列」です。このセクションでは、LIS（Longest Increasing Subsequence）として広く知られている最長部分列について学ぶことができます。

「LISって……？」となった方は、以下の記事も参考にしてみてください。

（参考）LISとは - 数学/競プロメモ

6：部分和問題

最後は「部分和問題」のセクションです。

このセクションには他のセクションと比べるとやや歯ごたえのある問題が用意されています。たとえば以下のような問題を扱っています。

1 ~ n の番号がついた n 個のおもりがあり、おもり i の重さは a_i です。
おもりを何個か選んで重さの和が x となるようにする方法を考えたとき、選ぶおもりの個数の最小値を出力してください。なお、同じおもりを2個以上選ぶことはできません。
なお、重さの和が x となるようにおもりを選ぶ方法が存在しない場合は-1と出力してください。