知名度がいまいち分かってないNextDPというテクニックについて

# はじめに
コード上では変数名として`NDP`であったり`NextDP`と名付けられやすいものです。
正式な名称はよく分かっていないですし、解説されたことがあるのかすら分かっていないテクニックなのですが、どの層でも役に立つもので、使い方やメリットを整理しておこうと思いました。
説明はPythonで行います。ChatGPT-4を使用してC++やRustに置き換えてもらっても動作したので、基本的には別の言語でも使用できるテクニックのはずです。

# 使い方について
まずは基本的なナップサック問題とそのコードを記載します。
実行速度の差をみたいため制約はすこし大きめです。

## 問題
 $N$ 個の品物があります。それぞれ重さが $w_i$, 価値が $v_i$ です。
重さの総和が $W$ を超えないように選んだ時の価値の総和の最大値を求めなさい。

### 制約
- $1 \le N \le 10000$
- $1 \le W \le 10000$
- $1 \le w_i \le 10000$
- $1 \le v_i \le 10^9$
- 入力は全て整数

## 一般的なコード(実行時間2000msほど)
```python
import random
random.seed(998244353) 
#NとWが最大のパターンの代わり
N=10000
W=10000
VW = []
for _ in range(N):
    VW.append([random.randint(1, 50),random.randint(1, 50)])
#基本的な解き方
DP = [[0]*(W+1) for _ in range(N+1)] #10001*10001の配列を作る
for i in range(N):
    v,w=VW[i]
    for j in range(W):
        DP[i+1][j]=max(DP[i+1][j],DP[i][j]) #i個目を入れないパターン
        if DP[i][j]>0 and j+w<=W: #i個目を入れるか試すパターン
            DP[i+1][j+w]=max(DP[i+1][j+w],DP[i][j]+v)
    if w<=W:
        DP[i+1][w]=max(DP[i+1][w],v)
print(max(DP[N]))
```

$DP[i$個目までの商品$][$重さ$]$で、2次元配列で価値の総和の最大を格納しています。
$i$個目までの商品を格納していますが、この遷移にて必要なのは毎回 $i - 1$ の情報のみです。
ずっと全ての情報を保持する必要はないということを考えると以下のように書き換えられます。

## NDPを使ったコード(実行時間700msほど)
```python
import random
random.seed(998244353) 
#NとWが最大のパターンの代わり
N=10000
W=10000
VW = []
for _ in range(N):
    VW.append([random.randint(1, 50),random.randint(1, 50)])
#NDPを使用した解き方
DP = [0]*(W+1) #初期配列を作る
for i in range(N):
    v,w=VW[i]
    NDP = [0]*(W+1) #次の遷移先の配列を作成する
    for j in range(W):
        NDP[j]=max(NDP[j],DP[j]) #i個目を入れないパターン
        if DP[j]>0 and j+w<=W: #i個目を入れるか試すパターン
            NDP[j+w]=max(NDP[j+w],DP[j]+v)
    if w<W:
        NDP[w]=max(NDP[w],v)
    DP=NDP #遷移先の配列を現在の配列扱いにする
print(max(DP))
```

添え字の`i`と`i+1`で遷移するのではなく、`DP`と`NDP`で遷移していきます。
このような書き方だと2次元配列を使うこともありません。

```python
for i in range(N):
    v,w=VW[i]
```
は、以下のように書き換えると添え字`i`もいらなくなります。
```python
for v,w in VW:
```



## NDPを使う場面について
ナップサックは2次元DPになりがちでi個目まで見た値を格納していきますが、2つ前の情報などは気にする必要は基本的にありません。
このように1つ前(2つ前もやろうと思えば可能…)の情報からしか遷移せず、それより前の情報を見ることがない場合のDPに使いがちかなと思います。
難易度が高い問題では大小両方向からアクロバティックに遷移するタイプのDPもあり、そういったDPに対しては使用することは出来ないので注意してください。


## 効果
- 添え字を気にする必要が1か所なくなるのでバグが減りやすい
- DPの次元を1つ落とせるので処理が早くなりTLEしなくなりやすい
- 巨大な配列を用意する必要が無くなるのでMLEしなくなりやすい

特に2次元配列や3次元配列のアクセスは遅くなりやすいPythonではお勧めの書き方です。


## 効果の例1
特にPythonで効果があるのでPythonを例にしてみます。
Pythonで競プロを行ってる人が基本躓く問題で確認して見ましょう。
（2020年の問題を未だに擦り続けてるのは老害みたいなものですが…）

https://atcoder.jp/contests/abc175/tasks/abc175_e

Pythonの提出はもちろんTLE、Pypyでは言語アップデートによりギリギリ間に合わないくらいになりましたが、MLEも起きてしまいます。

```python
R,C,K = map(int, input().split())
MAP = [[0] * (C+1) for _ in range(R+1)]
DP  = [[[0] * 4 for _ in range(C+1)] for _ in range(R+1)]
RCV = [list(map(int, input().split())) for _ in range(K)]
for r, c, v in RCV:
    MAP[r-1][c-1] = v
for i in range(R):
    for j in range(C):
        DP[i][j][3]=max(DP[i][j][3],DP[i][j][2]+MAP[i][j])
        DP[i][j][2]=max(DP[i][j][2],DP[i][j][1]+MAP[i][j])
        DP[i][j][1]=max(DP[i][j][1],DP[i][j][0]+MAP[i][j])
        DP[i][j+1][0]=max(DP[i][j+1][0],DP[i][j][0])
        DP[i][j+1][1]=DP[i][j][1]
        DP[i][j+1][2]=DP[i][j][2]
        DP[i][j+1][3]=DP[i][j][3]
        DP[i+1][j][0]=max(DP[i][j])
print(max(DP[R-1][C-1]))
```


- Pythonでの提出(TLE)

https://atcoder.jp/contests/abc175/submissions/49239063

- Pypyでの提出(TLEとMLE)

https://atcoder.jp/contests/abc175/submissions/49239061

ではこれをNextDPを使用したコードに置き換えてみました。
```python
R,C,K = map(int, input().split())
MAP = [[0] * (C+1) for _ in range(R+1)]
DP  = [[0] * 4 for _ in range(C+1)]
RCV = [list(map(int, input().split())) for _ in range(K)]
for r, c, v in RCV:
    MAP[r-1][c-1] = v
for i in range(R):
    NDP  = [[0] * 4 for _ in range(C+1)]
    for j in range(C):
        DP[j][3]=max(DP[j][3],DP[j][2]+MAP[i][j])
        DP[j][2]=max(DP[j][2],DP[j][1]+MAP[i][j])
        DP[j][1]=max(DP[j][1],DP[j][0]+MAP[i][j])
        DP[j+1][0]=max(DP[j+1][0],DP[j][0])
        DP[j+1][1]=DP[j][1]
        DP[j+1][2]=DP[j][2]
        DP[j+1][3]=DP[j][3]
        NDP[j][0]=max(DP[j])
    DP = NDP
print(max(DP[C-1]))
```

- NextDPを使用したPypyでの提出 (2000msほど改善)

https://atcoder.jp/contests/abc175/submissions/49239101

## 効果の例2
1/14にあったE問題の桁DPも1つ前のみからの遷移となるため`NDP`に置き換えることが可能です。
元が4次元のため、がっつり改善されるわけではないですが、ギリギリTLEしてるパターンについては役立つテクニックだと思います。

https://atcoder.jp/contests/abc336/tasks/abc336_e

- 元コード (5252ms)

https://atcoder.jp/contests/abc336/submissions/49304876


- `NDP`コード(4427ms)

https://atcoder.jp/contests/abc336/submissions/49320579

## ほかの例
`set`などでも使えます。直近の問題では以下のような使い方もできます。

https://atcoder.jp/contests/abc333/tasks/abc333_c

```python
N = int(input())
D = []
for i in range(1,13):
    D.append(int('1'*i))
S = set()
S.add(0)
for _ in range(3):
    NS = set()
    for s in S:
        for d in D:
            NS.add(s+d)
    S = NS
print(sorted(S)[N-1])
```

このテクニックを使ってない方は是非使ってみてください！

## 追記

この記事公開後にいくつか反応をいただきました。
他に使用される変数名では`dp2`、`pd`、`NewDp`、`PrevDp`など様々な種類があるようです。
C++の挙動など細かいことを理解していなかったこともあり、興味深かったり面白いポストがいくつかあったので以下に並べます。



<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">「Next DP」という言葉は実は今日初知り（調べたら、変数名ではけっこう使われてはいそうだった。用語として使われるのはすごく珍しい）</p>&mdash; はちじ@競プロ (@sad_eight) <a href="https://twitter.com/sad_eight/status/1747609337261076666?ref_src=twsrc%5Etfw">January 17, 2024</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">こないだの ABC 336-E の桁 DP で MLE やらかして、これをやりました……！！ <a href="https://t.co/21s0kGyBXy">https://t.co/21s0kGyBXy</a></p>&mdash; けんちょん (@drken1215) <a href="https://twitter.com/drken1215/status/1747620498857488408?ref_src=twsrc%5Etfw">January 17, 2024</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">この言語仕様の違い、 Python → C++ に移行する人がいたら罠になりうると思うので知っておくと良いかもです <a href="https://t.co/XwIiLLtKQs">pic.twitter.com/XwIiLLtKQs</a></p>&mdash; ごりちゃん🦍 (@prd_xxx) <a href="https://twitter.com/prd_xxx/status/1747620585453097447?ref_src=twsrc%5Etfw">January 17, 2024</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">ndp.assign(n, 0);<br>// 遷移<br>swap(dp, ndp);<br><br>とすると再確保が走らない</p>&mdash; 熨斗袋 (@noshi91) <a href="https://twitter.com/noshi91/status/1747619384665739646?ref_src=twsrc%5Etfw">January 17, 2024</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">業プロだとswap(dp,ndp)よりdp=move(ndp)の方が良さそうに見える</p>&mdash; ゴジラ＠競プロ (@gojira_kyopro) <a href="https://twitter.com/gojira_kyopro/status/1747619575859142947?ref_src=twsrc%5Etfw">January 17, 2024</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">Rust だと所有権システム的にもこの書き方が使いやすいので良い</p>&mdash; ま (@0x3b800001) <a href="https://twitter.com/0x3b800001/status/1747622448198041967?ref_src=twsrc%5Etfw">January 17, 2024</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">dpとnext_dpだけ持つやつ、ヒュの定数倍高速化典型っぽさある（AHC028でもやった）。あとは配列をstaticに確保して使い回したりとか</p>&mdash; TERRY (@terry_u16) <a href="https://twitter.com/terry_u16/status/1747620459779063947?ref_src=twsrc%5Etfw">January 17, 2024</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">ndp pdp の高速化で困るシーンよりも現代では復元で困るシーンがあるので配列沢山持ちがち。</p>&mdash; もすーん (@Mo_SoooN) <a href="https://twitter.com/Mo_SoooN/status/1747630827482071271?ref_src=twsrc%5Etfw">January 17, 2024</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">DP テーブルを直前と現在だけで使い回すの、自分は dp[prev][…]と dp[cur][…] として prev, cur を 0, 1 で交互に入れ替えながらやってる<a href="https://t.co/9ETXhM3dEh">https://t.co/9ETXhM3dEh</a></p>&mdash; ⚫️Y.Y.⚪️ (@ygussany) <a href="https://twitter.com/ygussany/status/1747612528442778098?ref_src=twsrc%5Etfw">January 17, 2024</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">蟻本に「DPにおける配列の再利用」として解説されてるので、名前はそれでいいかなという気がします。swapで実装するメリットはメモリ確保が減る点かな（定数倍の重い操作なので）。 <a href="https://t.co/p2CvDb7oHx">https://t.co/p2CvDb7oHx</a></p>&mdash; not (@not_522) <a href="https://twitter.com/not_522/status/1747623688613101998?ref_src=twsrc%5Etfw">January 17, 2024</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">JOIの問題はC++でもちょいちょいndp使わないと厳しいTLなことあるイメージ</p>&mdash; 趣味のキノコ (@Kinoko_kyoupro) <a href="https://twitter.com/Kinoko_kyoupro/status/1747619315971477795?ref_src=twsrc%5Etfw">January 17, 2024</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">nextDP のやつ、 X と nX だなー。<br>dp はアルゴリズムの名前だから変数名に使うのは違和感ある</p>&mdash; きり (@kiri8128) <a href="https://twitter.com/kiri8128/status/1747780637841625525?ref_src=twsrc%5Etfw">January 18, 2024</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">DPの更新先をNDPにする話で思い出したけど, 順列Pを更新していくタイプの問題だとP=NPとか書きがち.</p>&mdash; 仮の人数学+競プロ (@kari_math) <a href="https://twitter.com/kari_math/status/1747616052010438657?ref_src=twsrc%5Etfw">January 17, 2024</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>