この解き方は動的計画法でしょうか？

質問

動的計画法について勉強しているのですが、
どのような解法を動的計画法と呼んでいいのか、いまいち把握できずにいます。
動的計画法の定義は色々と読みはしたのですが・・・

というわけで、とにかく例をいくつも調べて感覚で覚えることにしました。
そこで質問なのですが。

整数列 [4, 6, 3, 1, 2] に対して、各値から、自身を含めた右全ての値の和の表を作るとします。
説明が下手で申し訳ないです・・・
この場合、答えは
4+6+3+1+2 = 16
6+3+1+2 = 12
3+1+2 = 6
1+2 = 3
2
と計算していって、 [16, 12, 6, 3, 2] という表を作りたいのです。

上の例では左から順に計算していったのですが、
これは右から順に求めていけば、計算がより簡単になると思います。
2
1+2 = 3
3+3 = 6
6+6 = 12
4+12 = 16

この考え方は動的計画法と言えるのでしょうか。

回答No.1

Tacosan · ベストアンサー

方向は逆ですけど, やってることは prefix sum ですね.
ん～, まぁ「動的計画法」と言えなくはないけど, あまりにも単純なので普通は言わないかな. なんというか, 「動的計画法」というともっと複雑 (例えば 2次元の表になっている) なものを想定するような気がするので.

お礼

回答ありがとうございます。
複雑さが足りない、ということは、一応考え方の方向性は合ってるのですね。
なんとなく掴めてきました。