Petitverse

配るDPと受け取るDPとメモ化再帰の違いが分からんって人にそれぞれの例を書いておく。
例えば、
「要素がnの配列がある。この配列のi番目の要素にi番目のリュカ数を20123で割ったあまりを代入せよ」
みたいな問題があったとき

配るDPで書くとこんな感じ。
option defint
input n
dim lucas[n]
lucas[0]=2:lucas[1]=1
for i=0 to n-2
　if i>0 then lucas[i+1]=(lucas[i+1]+lucas[i])mod 20123
　if i<n-2 then lucas[i+2]=(lucas[i+2]+lucas[i])mod 20123
next i

貰うDPで書くと
option defint
input n
dim lucas[n]
lucas[0]=2:lucas[1]=1
for i=2 to n-1
　lucas[i]=(lucas[i-1]+lucas[i-2])mod 20123
next i

メモ化再帰だと
option defint
input n
dim lucas[n]
lucas[0]=2:lucas[1]=1
def lucas(n)
　if lucas[n] then return lucas[n]
　lucas[n]=(lucas(n-1)+lucas(n-1))mod 20123
　return lucas[n]
end
tmp=lucas(n)

ちなみに、リュカ数は行列累乗でも解けますが、今回は議論の対象じゃないので省略。というか例の問題だとDPの方が速い。
一般項で求める方法も同じく。というか誤差が怖いし余りを求めるのは簡単じゃない。

やきはたさん
DPって大体漸化式のイメージあるけど、どうなんでしょう？

さすらいの名無しさん
DPはまず問題を小さく分割してから解いて、その小さい問題の計算結果を利用して最終的に大きい問題を解く手法のことです。
乱暴な言い方をすると、一度計算した結果を再利用するのがDP。

どこまでが動的計画法かが曖昧な部分はあると思いますが、上のコードもやってること自体はナップサックやDPコンのfrog(https://atcoder.jp:443/contests/dp/tasks/dp_a?lang=ja )とさほど変わらないような気がします。(違いと言えば問題を漸化式に変換する過程があるかどうか)
一応lucas[i-1]とlucas[i-2]という小さい問題の値を再利用しているので…DPってことにしていただけると助かる。

4次元位になると混乱するってのはとても共感。