だいなみっくぷろぐらみんぐ！！！！！！

はじめに

この記事はICT Advent Calender 2019の22日目の記事です。
昨日の記事はかりんと君が書いてくれました。

ka-rin-tou82.hateblo.jp

僕はノートPCを触っている時間が長くて慢性的な肩こりや首の痛みに悩まされているのでこの記事を参考にして自分の周りの環境を整えていきたいと思います。

ちなみに僕は魔剤を加湿器に入れる*1なんて頭のおかしい人ではありません。

忘れてたので pic.twitter.com/aTmuAr4w8Y
— otanjoumiko (@Yuuki_mnn) 2019年11月8日

...ん？

自己紹介

こんばんは。
最近学校に行くことへのモチベが下がりつつあるwakimikoです。
勉強自体が嫌なわけじゃなくて学校の課題や授業で自分の好きな分野の勉強ができないことが辛いねって感じです。

今回の記事でICTのアドベントカレンダーは3回目の参加になるんですが、前回と前々回どっちも1年の振り返りでした。
たまには違うやつも書きたいと思ったのでタイトル通りDPについて書きます。

DP（？）

DPは~~Dinamic~~Dynamic Programmingの略です。
Dynamicの意味は、三省堂大辞林第三版より

力強く，生き生きとしているさま。躍動的。力動的。

とあります。つまりDPとは、
全身を激しく動かし、キーボードを叩くのに全力を使ってプログラムを書く
行為のことを指します。

www.nicovideo.jp

つまり彼はDPがとても上手なつよつよプログラマーだったということになりますね。
以上、DPについての記事でした。

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　〜完〜

DP（本物）

このままだと殺されそうなので真面目に書きます。
DPとは、動的計画法と呼ばれるアルゴリズムの分類の1つです。
全探索などでは計算量が大きくて時間がかかってしまうような問題を小さい問題に分割して解き、その結果を用いて元の問題を解く手法です。
説明だけではわかりにくいので、実際の問題を考えながら解いていきましょう。

A - Frog 1
1番目の足場に乗っているカエルが、

次の足場へジャンプする
1つ飛ばして2つ隣の足場にジャンプする

の2つの行動でN番目の足場まで行くことを考えた時、それぞれコストが

$|h_i - h_{i+1}|$
$|h_i - h_{i+2}|$ 　（ $i$ は足場の番号）

の分1回ジャンプするごとにかかる。2つの行動を組み合わせてN番目の足場にたどり着く時の最小コストを求めろ、という問題です。

例として、 $N=6$ で、
$h_1$ から $h_6$ の数字がそれぞれ $30　10　60　10　60　50$ の場合を考えてみましょう。
まず、足場1からそれぞれの足場へ移動するときの最小コストを求めていきます。足場1から足場1へは、移動は必要ないのでもちろんコストは0です。

dp[6] = {0, INF, INF, INF, INF, INF}
// dp[n]はn番目の足場に移動する最小コスト

次に足場2への移動ですが、移動方法は足場1から移動する1通りしかないので、コストは $|30 - 10| = 20$ で確定です。

dp[6] = {0, 20, INF, INF, INF, INF}

足場3への移動方法は、足場1から1つ飛ばしで移動する方法と、足場2から移動する2通りあります。
足場1からだと
$|30 - 60| + 0 = 30 + 0 = 30$ (0は足場1から足場1への最小コスト)
足場2からだと
$|10 - 60| + 20 = 50 + 20 = 70$ (20は足場1から足場2への最小コスト)
になります。よって足場1からのコスト $30$ が最小コストです。

dp[6] = {0, 20, 30, INF, INF, INF}

同様に他の足場についても計算すると、足場4は足場2からの移動がコスト最小になり、

dp[6] = {0, 20, 30, 20, INF, INF}

足場5は足場3から、

dp[6] = {0, 20, 30, 20, 30, INF}

そして目的地の足場6は足場5からの移動が最小コストになります。

dp[6] = {0, 20, 30, 20, 30, 40}

こうして足場1から2, 3, 4とだんだん移動範囲を広げながら計算することで最終的に目的地の足場の最小コストを求めることができました。

このようにして小さい範囲の問題から解き、その計算結果を利用して元々の問題を解く手法がDPです。プログラムの流れとしては、

必要な情報を入力
dpに使う配列を初期化
ループなどを使って小さい範囲から計算
出力
の流れになると思います。以下、この問題をACするコードを載せます。

#include <stdio.h>
#include <math.h>

#define INF 10000000

int main(void)
{
    int n;
    int h[100010];
    int dp[100010] = {};
    int i;

    scanf("%d", &n);

    for (i = 0; i < n; i++) {
        scanf("%d", &h[i]);
        dp[i] = INF; // 配列をINFで初期化(未探索にする)
    }

    dp[0] = 0;
    dp[1] = abs(h[0] - h[1]); // 足場1から2への移動は1つなので確定

    for (i = 2; i < n; i++) {
        int first = dp[i-1] + abs(h[i-1] - h[i]); //一つ前からの移動
        int second = dp[i-2] + abs(h[i-2] - h[i]); //2つ前からの移動
        if (first < second) { // コストの小さい方を採用する
            dp[i] = first;
        }
        else {
            dp[i] = second;
        }
    }

    printf("%d\n", dp[n-1]);

    return (0);
}

なお、このプログラムは0-indexedなので、問題文の足場の番号と1ずれています。
気になる方は配列の添字を1から使うか、問題文の足場の数字を1引いて読み替えるなど工夫しましょう。

最後に

遅刻してごめんなさいいいいいいいいいいいいいいいいいいいいい
てか急いで書いたから解説が雑だしそもそも文章がものすごい読みにくい
とりあえず公開した後も何回か修正は入れるかも

メモ化再帰とかの話もやりたかったけど時間無いからまた別の機会に...

誤字報告や解説わかりにくいなどありましたらSlackかTwitterでよろしくおねがいします。

明日（今日）の記事はみずきち先輩です！！
---ここにはる---

shimamiz-m.hatenadiary.jp

*1 去年のPCKの時、ホテルで加湿器の隣に魔剤並べてツイッターに上げたらそういうことになった。もちろん今年もやった。