# (個人用)DP まとめ
## AtCoder の DP 問題
- [EDPC](https://atcoder.jp/contests/dp)
- [Dynamic Programming - AtCoder Tags](https://atcoder-tags.herokuapp.com/tags/Dynamic-Programming)
## DP のこころへ
1. dp テーブルの添字が何を示すのかを明確にしろ
2. dp テーブルがどのように遷移していくのかを明確にしろ
## EDPC
### A - Frog 1
#### 概要
足場 $1$ から足場 $N$ まで支払うコストの総和の最小値を求めましょう．
#### 小問題化とお気持ち
1. 足場 $N$ までのコストの総和の最小値
愚直にやったら $O(2^N)$...
2. 足場 $i$ までのコストの総和の最小値
3. **足場 $i-1$, $i-2$ までのコストの総和の最小値(足場 $i$ には $i-2$ と $i-1$ からしか行けないため)**
#### 入力例で考える
```
4
10 30 40 20
```
**dpテーブルの定義**
足場 $i$ までのコストの総和を $dp$ とし，$dp$ を要素数 $N$，要素それぞれを $\infty$ で初期化する.
**遷移**
足場 $i$ には足場 $i-2$ と足場 $i-1$ から行くことができる．このとき，$dp[i-2]$ と $dp[i-1]$ はそれぞれの足場までのコストの最小値であるため，これに $i$ までのコストを足してあげれば足場 $i$ までの最小値が求まる
$dp[i] = min(dp[i - 2] + abs(h[i] - h[i - 2]), dp[i - 1] + abs(h[i] - h[i - 1]))$
まず，🐸 の最初の足場は $1$ であるため，足場 $1$ までのコストは $0$ なので $dp[0] = 0$ となる．(0-indexed に注意)
次に，足場 $2$ を考える．足場 $2$ へは足場 $1$ からしか行くことはできないため，コストは $dp[1] = dp[0] + |h[1] - h[0]|$ となる．
次に，足場 $3$ を考える．足場 $3$ へは足場 $1$ と 足場 $2$から行くことができる．ここで，足場 $1$ までの最小コストは $dp[0]$，足場 $2$ までの最小コストは $dp[1]$，なので，$dp[2]$ までの最小コストは $dp[0] + |h[2] - h[0]|$ か $dp[1] + |h[2] - h[1]|$ のうち小さいほうとなる．
すなわち，足場 $i$ における最小コストは $min(dp[i - 2] + abs(h[i] - h[i - 2]),\ dp[i - 1] + abs(h[i] - h[i - 1])$ で表されるため，これをループで回した後の $dp[n - 1]$ が足場 $N$ までの最小コストとなる．
#### コード(Rust)
```rust=
#![allow(unused_imports)]
use proconio::{fastout, input, marker::*};
use std::collections::*;
#[fastout]
fn main() {
input! {
n: usize,
h: [i32; n],
}
// dp[i] ... 足場iにおけるコストの最小値
let mut dp = vec![i32::MAX; n + 1];
dp[0] = 0;
dp[1] = (h[1] - h[0]).abs();
for i in 2..n {
dp[i] = (dp[i - 2] + (h[i] - h[i - 2]).abs()).min(dp[i - 1] + (h[i] - h[i - 1]).abs());
}
println!("{}", dp[n - 1]);
}
```
### B - Frog 2
Frog 1 の $i-1$, $i-2$ を $i-1$, $i-2$, ..., $i-k$ にするだけ
### C - Vacation
#### 小問題化
最初に，$dp[i]$ = $i$ 日目における幸福度の最大値とおいたらだめ．同じ活動を2日連続できないという制約があるから，$i$ 日目に $j$ 活動を行ったときの幸福度の最大値を求めないとだめ．
1. $N$ 日目における幸福度の最大値を求めなさい．ただし，2日連続で同じ活動はできない．
$O(3^N)$！ｗ
2. **$i$ 日目に活動 $j$ を行ったときの幸福度の最大値を求めなさい**
#### サンプル
```
3
10 40 70
20 50 80
30 60 90
```
**dpテーブルの定義**
$i$ 日目に活動 $j$ を行ったときの幸福度の総和を $dp$ とし，$dp$ を要素数 ($N$, 3)，要素それぞれを $\infty$ で初期化する.
**遷移**
1日目は好きな活動を選ぶことができる．ここでは最大値である $70$ が選びたくなるが，$10$ を選んだときが最適になる可能性もあるため，すべての活動を選んだときの状態を $dp$ に入れる．すなわち，$dp[0][0] = a[0]$, $dp[0][1] = b[0]$, $dp[0][2] = c[0]$ となる．
2日目からは **2日連続して同じ活動をすることはできない** という制約が適用される．ここで，$dp[i][j]$ は $i$ 日目に活動 $j$ を選んだときの幸福度の総和であるため，2日目以降における活動の選び方は以下のようになる．
```
dp[i][0] = (dp[
- 1][1] + abc[i][0]).max(dp[i - 1][2] + abc[i][0]);
dp[i][1] = (dp[i - 1][2] + abc[i][1]).max(dp[i - 1][0] + abc[i][1]);
dp[i][2] = (dp[i - 1][0] + abc[i][2]).max(dp[i - 1][1] + abc[i][2]);
```
このようにして $N$ 日目まである活動を行ったときの幸福度の総和を求めることができたので，最終的な答えは $N$ 日目における活動のうち幸福度の総和が最大となっているものとなる．
**参考文献**
https://kyopro-friends.hatenablog.com/entry/2019/01/12/230931
#### コード(Rust)
```rust=
#![allow(unused_imports)]
use proconio::{fastout, input, marker::*};
use std::collections::*;
#[fastout]
fn main() {
input! {
n: usize,
abc: [[i32; 3]; n],
}
// dp[i][j] ... i日目に活動jを行ったときの幸福度の総和の最大値
let mut dp = vec![vec![std::i32::MAX; 3]; n];
dp[0][0] = abc[0][0];
dp[0][1] = abc[0][1];
dp[0][2] = abc[0][2];
for i in 1..n {
dp[i][0] = (dp[i - 1][1] + abc[i][0]).max(dp[i - 1][2] + abc[i][0]);
dp[i][1] = (dp[i - 1][2] + abc[i][1]).max(dp[i - 1][0] + abc[i][1]);
dp[i][2] = (dp[i - 1][0] + abc[i][2]).max(dp[i - 1][1] + abc[i][2]);
}
println!("{}", dp[n - 1].iter().max().unwrap());
}
```
### D - Knapsack 1
#### 小問題化
1. $0, 1, \cdots, N-1$ の中からいくつか選んだときの価値の総和の最大値を求めなさい．ただし，そのときの重さは $W$ 以下でなければならない．
bit全探索・・・？($O(2^N)$)
2. 重さの総和が $w(0\leq w\leq W)$ 以下になるように荷物を $i(0\leq i \lt N)$ 個選んだときの価値の総和の最大値を求めなさい．
$O(NW)$！！
#### サンプル
```
3 8
3 30
4 50
5 60
```
**dp テーブルの定義**
重さの総和が $w$ 以下となるように 最初から $i$ 個の中から選んだとき($0 \leq i \lt N$)の価値の総和の最大値を $dp[i][w]$ とする．サンプルだと以下のようになる.
> NOTE:
> $dp[i][w]$ はあくまで **最初から $i$ 個の中から** 選んだときの価値の総和の最大値である．
```
i/w
0 1 2 3 4 5 6 7 8 9 10 11 12
0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 30 30 30 30 30 30 30 30 30 30
2 0 0 0 30 50 50 50 80 80 80 80 80 80
3 0 0 0 30 50 50 50 80 90 90 90 90 140
```
**dp テーブルの遷移**
ある商品 $i$ を選ぶか選ばないかの2パターンで見ていく．
まず，$i$ を選ぶためには $w - weight[i] \geq 0$ を満たさなければならない．$i$ を選ぶことができるとき，最初から $i+1$ 個の中から選んだときの価値の総和の最大値は以下のようになる．
$dp[i+1][w] = min(dp[i + 1][w],\ dp[i][w - weight[i]] + value[i])$
<s>クッソわかりづらいんだが</s>
すなわち，以下の2つのうち，小さい方が $dp[i+1][w]$ として適する．
1. 重さの総和が $w$ 以下になるように最初から $i+1$ 個の中から選んだときの価値の総和の最大値
2. 重さの総和が $w - weight[i]$ 以下になるように最初から $i$ 個の中から選んだときの価値の総和の最大値
Sign in with Wallet
Connect another wallet