<jupyter_start><jupyter_text>メモABC 144 B - 81 * 動的計画法 DP Dynamic Programming* 定番アルゴリズム「DP（動的計画法）」をプログラミング練習問題集で学ぼう！* https://paiza.hatenablog.com/entry/2021/03/19/130000* https://paiza.jp/works/mondai/dp_primer/problem_index?language_uid=c-plus-plus* qiita 典型的な DP (動的計画法) のパターンを整理 Part 1 ～ ナップサック DP 編 ～<jupyter_code># 問題 動的計画法 DP でフィボナッチ数列を解く
%%writefile temp.cpp
# include <bits/stdc++.h>
using namespace std;

int fib(unsigned int n) {
    int memo[1000] = {0, 1}, i;
    for (i = 2; i <= n; i++) {
        memo[i] = memo[i - 1] + memo[i - 2];
    }
    return memo[n];
}
int main () {
    for (int i = 0; i < 10; i++) {
        cout << fib(i) << " ";
    }
    cout << endl; 
}
!g++ temp.cpp; echo  |./a.out
# 上のプログラムを理解するための実験
%%writefile temp.cpp
# include <bits/stdc++.h>
using namespace std;

int fib(unsigned int n) {
    int memo[1000] = {0, 1}, i;
    for (i = 2; i <= n; i++) {
        memo[i] = memo[i - 1] + memo[i - 2];
    }
    return memo[n];
}
int main () {
    vector<int> memo = {0, 1};
    for (int i = 2; i <= 10; i++) {
        memo[i] = memo[i - 1] + memo[i - 2];
    }
    for (int i = 0; i < 10; i++){
        cout << memo.at(i) << " ";
    }
    cout << endl;
}
!g++ temp.cpp; echo  |./a.out
定義を直接実装したプログラム
定義に基づいてプログラムを作成すると、次のようになる。

int fib(unsigned int n) {
    switch (n) {
        case 0: return 0;
        case 1: return 1;
        default: return fib(n - 1) + fib(n - 2);
    }
}
例えば、このプログラムを使ってフィボナッチ数列の第5項を求める場合を考えてみる。このプログラムは再帰的に呼び出されるので、その様子を以下に示す。

  fib(5) 
= fib(4) + fib(3) 
= (fib(3) + fib(2)) + (fib(2) + fib(1)) 
= ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1)) 
= (((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1)) 
このように最終的に fib(0) と fib(1) の呼び出しに収束し、fib(0) と fib(1) の呼び出し回数の和が結果の値となる。
この方法を用いたフィボナッチ数列の計算量は {\displaystyle O(2^{n})}O(2^{n}) の指数関数時間となる。

動的計画法を利用したプログラム（ボトムアップ方式）
int fib(unsigned int n) {
    int memo[1000] = {0, 1}, i;
    for (i = 2; i <= n; i++) {
        memo[i] = memo[i - 1] + memo[i - 2];
    }
    return memo[n];
}
fib(n - 1) と fib(n - 2) を先に計算しておいた上で、fib(n) を計算している。この場合は先ほどの実装と異なり、
ループ部分の計算量は O(n) の多項式時間である。このように指数関数時間で行われる処理を、計算済みの結果を記録することにより多項式時間で処理できるように改良でき、計算時間を圧倒的に減らせる。

動的計画法を利用したプログラム（トップダウン方式）
トップダウンで、メモ化を併用したやり方。fib(n) を計算するのに、fib(n - 1) と fib(n - 2) が必要だが、計算結果を配列 memo に保存して再利用している。

#include <stdbool.h>

int memo[1000] = {0, 1};
bool in_memo[1000] = {true, true};

int fib(unsigned int n) {
    if (!in_memo[n]) {
        memo[n] = fib(n - 1) + fib(n - 2);
        in_memo[n] = true;
    }
    return memo[n];
}
近年は色々なプログラミング言語がメモ化を言語レベルでサポートしている。その機能を利用した場合、より簡単に書ける場合がある。例えば Groovy の場合、@Memoized を付けることでメモ化するが、下記のように、定義を直接実装したプログラムに @Memoized を付けると動的計画法になる。

import groovy.transform.Memoized

@Memoized
int fib(int n) {
    switch (n) {
        case 0: return 0
        case 1: return 1
        default: return fib(n - 1) + fib(n - 2)
    }
}
関連項目
分割統治法
メモ化
チャートパーサ - CYK法、アーリー法
ビタビアルゴリズム
貪欲法
DPマッチング
参照
^ <NAME>, An introduction to the theory of dynamic programming, The Rand Corporation, Santa Monica, Calif., 1953
^ <NAME>, The theory of dynamic programming, Bull. Amer. Math. Soc. 60 (1954), 503-515
表話編歴
アルゴリズム
表話編歴
数理最適化 • 最適化問題 : メソッド • ヒューリスティクス
典拠管理 ウィキデータを編集	
BNE: XX543843BNF: cb11978098s (データ)GND: 4125677-3J9U: 987007567971605171LCCN: sh85040313NDL: 00571739
カテゴリ: オペレーションズリサーチ最適化アルゴリズムリチャード・E・ベルマン
案内メニュー
Katsu95i
アラート (0)
通知 (0件)
会話
下書き
個人設定
ベータ版
ウォッチリスト
投稿記録
ログアウト
ページノート
閲覧編集履歴表示ウォッチリストに追加
検索
Wikipedia内を検索
メインページ
コミュニティ・ポータル
最近の出来事
新しいページ
最近の更新
おまかせ表示
練習用ページ
アップロード (ウィキメディア・コモンズ)
ヘルプ
ヘルプ
井戸端
お知らせ
バグの報告
寄付
ウィキペディアに関するお問い合わせ
ツール
リンク元
関連ページの更新状況
DP（動的計画法）とは
こういうときはひとまず Wikipediaを見てみましょう。DPとはなにものかについてこう書かれています。

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

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

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

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

（参考）うさぎでもわかるアルゴリズム　動的計画法
レベルアップ問題集とは
「DPメニュー」は、レベルアップ問題集にて公開しています。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

20210312102220

最初の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種類以上に増えた場合など、さまざまなバリエーションの問題を用意しています。

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

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

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

20210312103702
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 とします。
背の順であるような区間のうち、最長であるものの長さを出力してください。

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

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

20210312110934

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

（参考）LISとは - 数学/競プロメモ
6：部分和問題
最後は「部分和問題」のセクションです。

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

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

20210312111322

今この問題を見て「自分には難しそうだな...」と思った方でも、DPメニューを最初からていねいに取り組んでいけばこの問題が自力で解けるようになるはずです。

まとめ
レベルアップ問題集に追加された「DPメニュー」について紹介してきました。

はじめてこういったアルゴリズムの問題に取り組む場合、最初はなかなか理解が進まずもどかしいかもしれませんが、解説や解答コード例も参考にぜひ何度もチャレンジして力をつけていっていただければと思います。

ちなみにpaizaラーニングの動画講座「アルゴリズム入門編」では、DPメニューで扱った漸化式の定番問題である「フィボナッチ数」を解説しています。

興味がある方はこちらもチェックしてみてくださいね。

20210318140548

プログラミングを始めたばかりで問題集の内容が難しいと感じた方は、まずは基礎文法からしっかり身につけるのもよいでしょう。

paizaラーニングでは、Python・PHP・Ruby・Java・C・C#・JavaScriptの7言語の入門講座を公開していますので、ぜひご活用ください。プログラミング言語入門講座一覧はこちら

paizaラーニング

*1:ただし、それらを閲覧するためには学習チケットが必要となります。チケットは毎日初回ログイン時に1枚付与され6枚まで所持できます。（有料会員の場合はチケットの消費なしで閲覧可能です）

動的計画法
 
プログラミング学習
 
プログラミング問題
 
アルゴリズム
paiza 1年前


little_strange
little_strange
little_strange
skiesotter
toomath
toomath
   
関連記事
グラフを隣接行列・隣接リストで実装しよう！アルゴリズムを学べるプログラミング問題集
2022-03-01
グラフを隣接行列・隣接リストで実装しよう！アルゴリズムを学べるプログラミング問題集
こんにちは。倉内です。ある程度プログラミングの基本を学び終…
プログラミング問題を解いてAmazonギフト券を当てよう！レベル別勉強法も紹介
2022-02-14
プログラミング問題を解いてAmazonギフト券を当てよう！レベル別勉強法も紹介
こんにちは。倉内です。paizaでは、本日よりプログラミング問題…
完全無料のプログラミング練習問題集「レベルアップ問題集」で実力を鍛える！
2021-12-02
完全無料のプログラミング練習問題集「レベルアップ問題集」で実力を鍛える！
こんにちは。倉内です。プログラミングの勉強方法はさまざまで…
効率的な「ソートアルゴリズム」を学ぶ！プログラミング問題集公開
2021-06-14
効率的な「ソートアルゴリズム」を学ぶ！プログラミング問題集公開
こんにちは。paizaラーニングでコンテンツ制作をしている学生ス…
探索アルゴリズムの基本「線形探索」を練習問題集で学ぼう
2021-05-07
探索アルゴリズムの基本「線形探索」を練習問題集で学ぼう
こんにちは。paizaラーニングでコンテンツ制作をしている学生ス…
コメントを書く
« 30代のエンジニアが面接をうまく乗り切る…
エンジニアに向いているのは「プログラミ… »

paiza転職
paiza新卒
EN:TRY
paizaラーニング
Tech Team Journal
paizaラーニングの人気講座
Python入門編
Java入門編
PHP入門編
C#入門編
JavaScript入門編
Python×AI・機械学習入門編
カテゴリー
paiza (208)
paiza-PaizaCloud (29)
paiza-イベント告知/レポート (166)
paiza-オンラインハッカソン (38)
PaizaCloud-tutorial (16)
その他 (88)
その他-DX (3)
その他-アニメ/漫画 (11)
その他-ネタ (60)
その他-連載：すべてうまくいく (10)
キャリア・働き方 (352)
キャリア・働き方-ITエンジニアのキャリア (275)
キャリア・働き方-ITエンジニアの健康 (12)
キャリア・働き方-リモートワーク (13)
キャリア・働き方-既卒 (8)
キャリア・働き方-第二新卒 (77)
キャリア・働き方-起業/スタートアップ (6)
プログラミング (622)
プログラミング-プログラミング初心者 (497)
プログラミング-プログラミング学習 (548)
プログラミング-プログラミング教育 (30)
プログラミング-競技プログラミング (5)
採用企業向け (50)
採用企業向け-ITエンジニアの採用 (48)
転職・就職 (450)
転職・就職-ITエンジニアの転職 (284)
転職・就職-内定者インタビュー (16)
転職・就職-新卒/就活 (165)
転職・就職-転職者インタビュー (19)
転職・就職-面接対策 (106)
開発ネタ (605)
開発ネタ-Docker (9)
開発ネタ-MEANスタック (3)
開発ネタ-UI/UX (6)
開発ネタ-Webサービス紹介 (458)
開発ネタ-Webデザイン (28)
開発ネタ-アルゴリズム (28)
開発ネタ-ストラテジ (1)
開発ネタ-ディレクション (5)
開発ネタ-ノーコード (4)
開発ネタ-フレームワーク (15)
開発ネタ-マネジメント (5)
開発ネタ-企画 (2)
開発ネタ-暗号通貨 (8)
開発ネタ-書籍紹介 (90)
開発ネタ-機械学習 (38)
開発ネタ-環境 (28)
開発ネタ-著作権 (1)
検索
記事を検索
月別アーカイブ
▶ 2022 (81)
▼ 2021 (174)
2021 / 12 (16)
2021 / 11 (14)
2021 / 10 (14)
2021 / 9 (14)
2021 / 8 (13)
2021 / 7 (14)
2021 / 6 (14)
2021 / 5 (12)
2021 / 4 (14)
2021 / 3 (16)
2021 / 2 (16)
2021 / 1 (17)
▶ 2020 (263)
▶ 2019 (240)
▶ 2018 (220)
▶ 2017 (235)
▶ 2016 (166)
▶ 2015 (143)
▶ 2014 (60)
▶ 2013 (9)
最新記事
本気で未経験からエンジニアを目指す人向け「転職前に知っておきたい適性・独学・年収の話」
2022-05-20
本気で未経験からエンジニアを目指す人向け「転職前に知っておきたい適性・独学・年収の話」 はてなブックマーク - 本気で未経験からエンジニアを目指す人向け「転職前に知っておきたい適性・独学・年収の話」
JavaScriptで独自機能も追加できる無料のWebデザインエディタ「Vev」を使ってみた！
2022-05-18
JavaScriptで独自機能も追加できる無料のWebデザインエディタ「Vev」を使ってみた！ はてなブックマーク - JavaScriptで独自機能も追加できる無料のWebデザインエディタ「Vev」を使ってみた！
学生・新人エンジニア向け・初心者でも無料でRubyを学べる5つの入門学習コンテンツ
2022-05-16
学生・新人エンジニア向け・初心者でも無料でRubyを学べる5つの入門学習コンテンツ はてなブックマーク - 学生・新人エンジニア向け・初心者でも無料でRubyを学べる5つの入門学習コンテンツ
アルゴリズムの計算量とO記法を動画で学ぼう！プログラミング練習問題も紹介
2022-05-13
アルゴリズムの計算量とO記法を動画で学ぼう！プログラミング練習問題も紹介 はてなブックマーク - アルゴリズムの計算量とO記法を動画で学ぼう！プログラミング練習問題も紹介
注目記事
JavaScriptで独自機能も追加できる無料のWebデザインエディタ「Vev」を使ってみた！JavaScriptで独自機能も追加できる無料のWebデザインエディタ「Vev」を使ってみた！ はてなブックマーク - JavaScriptで独自機能も追加できる無料のWebデザインエディタ「Vev」を使ってみた！
「技術のスペシャリスト」になれないエンジニアのキャリアを考える「技術のスペシャリスト」になれないエンジニアのキャリアを考える はてなブックマーク - 「技術のスペシャリスト」になれないエンジニアのキャリアを考える
SQLの練習に最適！ブラウザ上で実行できる初心者向け学習サービス5選SQLの練習に最適！ブラウザ上で実行できる初心者向け学習サービス5選 はてなブックマーク - SQLの練習に最適！ブラウザ上で実行できる初心者向け学習サービス5選
【新卒向け】最終面接で落とされる率がぐっと下がる3つの対策【新卒向け】最終面接で落とされる率がぐっと下がる3つの対策 はてなブックマーク - 【新卒向け】最終面接で落とされる率がぐっと下がる3つの対策
初心者向け・Pythonの練習問題をたくさん解ける学習サイト7選初心者向け・Pythonの練習問題をたくさん解ける学習サイト7選 はてなブックマーク - 初心者向け・Pythonの練習問題をたくさん解ける学習サイト7選
JavaScriptで壮大なハッキング体験を実現するWebゲーム「Bitburner」で遊んでみた！JavaScriptで壮大なハッキング体験を実現するWebゲーム「Bitburner」で遊んでみた！ はてなブックマーク - JavaScriptで壮大なハッキング体験を実現するWebゲーム「Bitburner」で遊んでみた！
文系学生から新卒でエンジニアになって2年8ヶ月で辞めた話をします文系学生から新卒でエンジニアになって2年8ヶ月で辞めた話をします はてなブックマーク - 文系学生から新卒でエンジニアになって2年8ヶ月で辞めた話をします
独自Webアプリや社内ツールが作り放題のオープンソース開発環境「ToolJet」を使ってみた！独自Webアプリや社内ツールが作り放題のオープンソース開発環境「ToolJet」を使ってみた！ はてなブックマーク - 独自Webアプリや社内ツールが作り放題のオープンソース開発環境「ToolJet」を使ってみた！
【C言語】データ構造の基本を学ぼう！スタックとキューを配列で実装する【C言語】データ構造の基本を学ぼう！スタックとキューを配列で実装する はてなブックマーク - 【C言語】データ構造の基本を学ぼう！スタックとキューを配列で実装する
面倒な手続き不要！「Web API」の超お手軽活用術をJavaScriptコード付きで一挙大公開！面倒な手続き不要！「Web API」の超お手軽活用術をJavaScriptコード付きで一挙大公開！ はてなブックマーク - 面倒な手続き不要！「Web API」の超お手軽活用術をJavaScriptコード付きで一挙大公開！
プロフィール
id:paiza
paiza はてなブログPro
paizaの中の人たちが書いています

読者になる3574
このブログについて

paizaのおすすめコンテンツ
Webセキュリティ入門 ハッカー入門
Webセキュリティ講座がスタート！CVは内田真礼さん！
Python✕AI 機械学習入門講座
CVに上坂すみれさんを起用！人気の機械学習講座を公開中！
paiza転職
paiza新卒
EN:TRY
paizaラーニング
記事内に記載している情報は、記事公開時点でのものとなります。
Copyright Paiza, Inc, All rights reserved.<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.10763032395987503, 'fraction_numerical': 0.05862522611412597, 'mean_word_length': 6.918619791666667, 'pattern_counts': {'":': 0, '<': 30, '<?xml version=': 0, '>': 11, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '399945', 'license': 'MIT', 'n_tokens_mistral': 10758, 'n_tokens_neox': 10082, 'n_words': 882, 'path': 'cpp_dynamicprogramming.ipynb', 'repo_name': 'kalz2q/myjupyternotebooks', 'size': '12180'}