動的計画法の学習方法、納得感について

Question

実現したいこと

動的計画法(dp)の学習を3日前からしているのですが、ふと疑問に思ったことがあるのと皆さんがどのように学習したのかを知りたいと思い質問させていただきました。

dpを三日前から勉強しており、chatGPTに問題の作成を依頼し考え方があっているのかを都度フィードバックを受けるようにしています。
また、問題文の難易度も同時に出力してもらっていて初級レベルの問題なのですが、モチベーション維持も兼ねて伺いたいことがあります。
私はdpの問題を実際に手を動かして解決する際には直感的なイメージをアルゴリズムに起こそうとしています。
他のアプローチとしてはdp表を思い浮かべて忠実に再現するというのもあると思うのですが、どちらの方がいいのかというのはあるのでしょうか？
というのも、アルゴリズムの理解として自分が納得できないと中々身につかないなと思い、半年前くらいにも一度dpにチャレンジしてみたものの挫折してしまいました。

ここに実現したいことを箇条書きで書いてください。

今回解いた問題としては以下の問題があります。

(1) 部分和問題（部分集合和）

N個の正の整数 a_1, a_2, ..., a_N が与えられます。
これらのうちいくつかを選んで、ちょうど合計 S にできるか判定してください。

(2) 階段の上り方

N段の階段があります。
一度に1段か2段ずつ上ることができます。
N段目に到達する方法は何通りあるか求めてください。

(3) コイン問題（最小枚数）

N種類のコインがあります。
それぞれのコインの価値は coins = [c1, c2, ..., cN] です。
合計金額 M を作るときに必要なコインの枚数の最小値を求めてください。
作れない場合は -1 を返してください。

---

(1)の問題について私の直感的な感覚を説明します。dpを学び始めているというのも含めて。

まず、ループにおいてひとつ前のループを現在のループで使用するのだろうと考えました。
ただ、dp[index]を0からというのを利用して更新していくことは不可能だと思ったので、a_xで更新していくのだろうと考えました。
また「前回の値」+a_xの値を合計することで部分和を求めていくのだろうと思いました。
最終的には、挫折したのですがイメージとしては

dp[0] = true
for i in 0.. A.size -1
  for j in S downTo 0
    if (dp[j] == true) and  (j + A[i] <= S)
      dp[j + A[i] = true

というものですが、いわゆるdp表といわれる
A.size * Sの表を埋めていくものとは違っています。
将来的難易度があがるにつれて、二次元のdp配列が必要な場合もあるのかもしれません。
正直に言うと逆にdp表を埋めるアルゴリズムがいまいち分かっていませんが、現在理解をすべきでしょうか？
納得できるような問題が出たときでよいのでしょうか。
また、直感的にdp表に起こす気にならない理由など思い当たる部分はありますか？

(1)皆さんがdpを学習したときの方法について
(2)直感が大事か？dp表も大事か？皆さんがアルゴリズムの発想をする際にイメージするのはなにか？
(3)どういった形式の問題なら直感とdp表のギャップを埋められるか？また何故このような思考の違いがでるのか？

込み入った内容ではありますが、特に回答方法等指定いたしておりませんので何かアドバイスを伺えればと思います。

ご回答よろしくお願いいたします。

前提

• 質問文には疑似コードを記載させていただきましたが、回答の際に言語は問いませんしこちらでも調べるのでご自由にお書きください
• 数学のレベルが極めて低い自覚があるのですが、もし回答に必要でしたら必要な単元を何卒記載いただけると幸いです
• 回答に際してご質問がある際はご遠慮なくお申し付けください。

発生している問題・エラーメッセージ

将来的にはおそらくGPTの出力内容も誤ったものになるのだろうという危惧もあります。
dpの問題はよく目にするのでどこかのタイミングで一度理解していたいと思っています。
サブの課題ですがデータ構造とアルゴリズムの問題について一般的なレベルでは難なく解けるようになりたいと思っています。

試したこと

分からないときは一度期間を開けるようにして解決することもありますが、dpの問題はどん詰まりなイメージです。
現在は今回の学習している内容的には少しずつ成長が実感できているところではあります。

補足情報（FW/ツールのバージョンなど）

最終的にはAtCoderを使用して問題を解けるか、すっきりするかをテストしていきたいと考えています。

コメント返信を転記

Q. ｢挫折した｣のにそのイメージに拘る理由は何でしょうか？そこが｢納得感｣とやらに関連している気がするのですが。
A. 挫折したのにイメージにこだわる理由は、回答に納得できるからです。
何といえばわかりやすいのか分かりませんが、Aの道とBの道を選んで、Aの道の通り方が一切わからない、Bの道の通り方はなんとなくイメージはつかめている、Bの道を最後まで行けなくとも、答えだけ見るとBの方が納得できた。そういうことです。
dp表の方は頭の中で現状勉強不足なのも含めて再現できないので、先のコメントと少しかぶるのですが、直感的なやり方で解決できるのであればセオリーにこだわらなくてよいのか？というのは疑問です。応用で使うのであれば結局そこでは納得感は生まれるはずなので、興味関心も含めて意見を伺いたいです。

Q. 質問記載のdp表の意味が分からない
A. 私の方でもdp表のアルゴリズムに納得、理解していないので説明させるのは酷だと思いますが動的計画法は全探索すると組み合わせ爆発が起きる問題において、任意の計算結果を求めるのに、ステップごとに分けることで、N ＊ Mの範囲に収めることができるアルゴリズムです。
数列がa_1, a_2, a_nとあって、その組み合わせで合計Mを作れるか？という問題においては、
a_1, a_2の列、合計0..Mの行からなる表を作成し埋めていくことで、N列M行を見れば最終的な結果が分かるというアルゴリズムになります。(行列は転置してもいいと思いますが、どっちがセオリーかはよく知りません。)
これは要するに二次元配列にマッピングし逐次的にマスを埋めるアルゴリズムをプログラム的には書くことができます。
私が質問文に書いた(1)の解法としてもこれはdpと呼べると思います。
よく考えたらこの解き方自体、別の問題の派生でその時に動的計画法という言葉を知らなかったのでこの書き方を発想してしまうのかもしれません。
皆さんはアルゴリズムの勉強か何かで配列のインデックスの方を着目して、要素を埋めるという解法を通っていない、つまり一般的な方法ではないという形になるのでしょうか。C言語を学んでいるときに通ったのですが。

コメント返信時の補足

後出しで申し訳ないのですが、問題を説明しているサイトを見るとか、本を見るという点においてですが、著者が天才なのか自分が数学の教養がないのか細かいところが気になりすぎて、どうしても牛歩になってしまいます。
アルゴリズムの問題ですので実際にプログラムを書かなくても、勉強はできるはず。。。と思いGPTに先生をやってもらっていますが、結局問題を解こうとするうちにやる気が上がってPCを開いてしまいます。
でも、この勉強法でも今のところいいと思っています。少なくとも前に進んでいる感覚があるので。

よろしくお願いいたします。

Comments

[fana]

話がイマイチわかりません．

> 私はdpの問題を実際に手を動かして解決する際には直感的なイメージをアルゴリズムに起こそうとしています。
> 他のアプローチとしてはdp表を思い浮かべて忠実に再現するというのもあると思うのですが、どちらの方がいいのかというのはあるのでしょうか？

（当方，先ほど「動的計画法」でググった程度のバカですので）
「dp表を思い浮かべて忠実に再現する」っていう話が，どういう意味なのかまるでわからないのですが……

【「dp表を思い浮かべて～」と「直感的な～」という２つの異なる方法が思いつくが，どっちを使えばいいのか？】
みたいなことを言っているのですか？
だとしたら，そんなの　好きな方/制約に見合う方　でやれば？　っていうだけになりそうですが．
例えば「何らかの効率が要求されている場面であれば，より効率の良い側を選べばいいよね」っていう．

[fana]

「dp表」とかいう何かが，「何かしらの途中計算結果を再利用するために記録しておくための記憶領域」みたいな物のことを指すのであれば，

> dp表を思い浮かべて

とかいう時点で既に「こういう順で計算を進めていって，こういう情報を記録していけばいいよね」的な手順（：アルゴリズム）が見えている，っていう話なのでしょうから，「納得感」もクソも無いように思うのですが…？
（その手順で解けるということはわかるけども，何かが納得できない？　　どういう意味？）

[meg_]

> 最終的には、挫折したのですがイメージとしては
｢挫折した｣のにそのイメージに拘る理由は何でしょうか？そこが｢納得感｣とやらに関連している気がするのですが。

[fana]

> いわゆるdp表といわれる A.size * Sの表

これもわからん（…のは私がDPを知らないからなのかな？）．
必要な表（記憶域）のサイズというのは完全に問題依存（というか解き方依存とでもいうか）なのではないのだろうか？

[fana]

なんかわからんけども，おそらく似たような（あるいは意味的に同じ）問題をＤＰで解く話を説明しているような場所とかがあるんじゃないかな？　とか思うので，そういうのを読んでみるとか．

（とりあえず「動的計画法」でググると大抵の場所で「フィボナッチがどうの～」という例の話をし始めていて，その次に何か別の問題の例を持ってくるような構成が多い様子？）

[u2025]

Q. ｢挫折した｣のにそのイメージに拘る理由は何でしょうか？そこが｢納得感｣とやらに関連している気がするのですが。
A. 挫折したのにイメージにこだわる理由は、回答に納得できるからです。
何といえばわかりやすいのか分かりませんが、Aの道とBの道を選んで、Aの道の通り方が一切わからない、Bの道の通り方はなんとなくイメージはつかめている、Bの道を最後まで行けなくとも、答えだけ見るとBの方が納得できた。そういうことです。
dp表の方は頭の中で現状勉強不足なのも含めて再現できないので、先のコメントと少しかぶるのですが、直感的なやり方で解決できるのであればセオリーにこだわらなくてよいのか？というのは疑問です。応用で使うのであれば結局そこでは納得感は生まれるはずなので、興味関心も含めて意見を伺いたいです。

Q. 質問記載のdp表の意味が分からない
A. 私の方でもdp表のアルゴリズムに納得、理解していないので説明させるのは酷だと思いますが同的計画法は全探索すると組み合わせ爆発が起きる問題において、任意の計算結果を求めるのに、ステップごとに分けることで、N ＊ Mの範囲に収めることができるアルゴリズムです。
数列がa_1, a_2, a_nとあって、その組み合わせで合計Mを作れるか？という問題においては、
a_1, a_2の列、合計0..Mの行からなる表を作成し埋めていくことで、N列M行を見れば最終的な結果が分かるというアルゴリズムになります。(行列は転置してもいいと思いますが、どっちがセオリーかはよく知りません。)
これは要するに二次元配列にマッピングし逐次的にマスを埋めるアルゴリズムをプログラム的には書くことができます。
私が質問文に書いた(1)の解法としてもこれはdpと呼べると思います。
よく考えたらこの解き方自体、別の問題の派生でその時に動的計画法という言葉を知らなかったのでこの書き方を発想してしまうのかもしれません。
皆さんはアルゴリズムの勉強か何かで配列のインデックスの方を着目して、要素を埋めるという解法を通っていない、つまり一般的な方法ではないという形になるのでしょうか。C言語を学んでいるときに通ったのですが。

疑問点は解消されましたでしょうか。
こちらからも質問があるのですが、質問文の方はそのままでよいでしょうか。段落を分けるなどの改善点が自分の中ではあるのですが、逆に読みづらくなる可能性もあるので、せっかくならついでにお伺いしたいです。

また後出しで申し訳ないのですが、問題を説明しているサイトを見るとか、本を見るという点においてですが、著者が天才なのか自分が数学の教養がないのか細かいところが気になりすぎて、どうしても牛歩になってしまいます。
アルゴリズムの問題ですので実際にプログラムを書かなくても、勉強はできるはず。。。と思いGPTに先生をやってもらっていますが、結局問題を解こうとするうちにやる気が上がってPCを開いてしまいます。
でも、この勉強法でも今のところいいと重いっています。少なくとも前に進んでいる感覚があるので。

よろしくお願いいたします。

[quickquip]

> 私はdpの問題を実際に手を動かして解決する際には直感的なイメージをアルゴリズムに起こそうとしています。
> 他のアプローチとしてはdp表を思い浮かべて忠実に再現するというのもあると思うのですが、どちらの方がいいのかというのはあるのでしょうか？

これは自分の直感的なイメージがDPにおける表と結びついてない、と言ってますか?
直感的なイメージがDPの表に結びついてないなら、それは「動的計画法で解こうとしていない」と同義ですよね?

私は動的計画法と関係ない手法をイメージして解こうとしています。
だから動的計画法でいうところの表を埋めていくものと違うものになります。
だから動的計画法で解くイメージが湧きません。

素直に読むと、こう要約されると思うのですが合ってますか?

[fana]

少なくとも(1)の問題で２次元の広大な記憶域が必要になるとも思えないですし，１次元でやれるならそれでいいじゃないですかね？
（せいぜい要素数Ｓ，あるいは番兵的なのを要するとしても S+1 とかの１次元配列で十分）

素人目には，記憶域が１次元だろうが２次元だろうが３次元だろうが「動的計画法」という言葉の範囲内にあるんじゃないかと思えます．
（ググって出てくる「フィボナッチ～」は一次元ですよね）

> 質問文の方はそのままでよいでしょうか

何かを追記したり，構成を変えることで内容がより伝わりやすくなると思われるのであればそのようにすれば良いかと思います．
（ただ，あまりにも変更されてしまうと，それはそれで，変更前に書かれたコメント等の意味が後から読む人にわからなくなり得るという点には注意が必要かな，と．）

[u2025]

申し訳ありません。
コメントの方読んでいますが、また後程返信させてください。
よろしくお願いいたします。

[fana]

> 皆さんはアルゴリズムの勉強か何かで配列のインデックスの方を着目して、要素を埋めるという解法を通っていない、つまり一般的な方法ではないという形になるのでしょうか。C言語を学んでいるときに通ったのですが。

「回答」とした文内にも書いたけども，ある方法が「ＤＰ」なる言葉の範囲に収まるのか否か，なんてことは，ふつーは　至極どうでもいい　というか，そんなことを考えることすらしない　と思うんですよね．
何らかの一時的な結果を保持するために配列を使うなんてことは，何も特別なことでもなく，ごくごく一般的な話/誰だって自然に行うようなこと でしかないので，そこに何か名前を付けて特別視するような事柄でもないです．

---

「ＤＰ」なる語の定義が実際にどんなものであろうが，「それを」学ぶという目的で練習しているのであれば「それを」使うべきなのでしょうから，あなたが直感的に思いつく方法がそれと同じだろうが異なっていようがやるべきことに影響は無いですよね．常に「ＤＰ」側一択です．で，その内容を納得しなければそもそも 練習/学習 にならないのでは．
本件の場合，そもそも目的が「問題を解くこと」ではなくて，「問題を　DPで解く/解けるようになる　こと」なハズなので．

[meg_]

> 挫折したのにイメージにこだわる理由は、回答に納得できるからです。
私には解にたどり着けない方法を正しいと思うことが理解できません。挫折→回答に納得、も飛躍していて理解できません。すみませんがここで失礼します。

[u2025]

@fanaさん、@meg_さん、
迷惑なのでお引き取りください。
不愉快で憤りを感じたのでスマホからですが返信致します。

@quickquipさん
DP表が動的計画法の全てという話でないかと思うので、動的計画法でとこうとしていないという話しではありません。DP表に起こせないという話を言い換えただけだと思いますが、@fanaさんもそうですが動的計画法の細微な定義をこねくり回すことの何が楽しいのか微塵も理解出来ません。
※攻撃的な表現でしたら申し訳ありません。続く2人の返信に怒りを覚えています。

@fanaさん
そんな話はしていません。迷惑なのでお引き取りください。

@meg_さん
理解できないのであれば学習をしてください。
尚、解決の方法の話ではなくアルゴリズムの方法とアルゴリズムの答えとしての話を混ぜて考えないでください。DP表という方法、直感という方法という話が出たのでそれを引き摺って、回答自体の納得感と導き方を混ぜたのかもしれませんが。
返信は結構です。

[u2025]

なぜ初心者目線で考えずに、こんなにすぐに返信することができるんだろう？
忘れていくのは仕方ないけれど、今の自分が理解できないからと言って過去に通った道なのだから、もう少し寄り添うことも出来ないはずが無いのに。
お互い様でしょうが嫌がらせのためにコメントを書いているようにしかうつらない。人の気持ちを考えることが出来ないのだろうか。

[fana]

> 迷惑なのでお引き取りください

了承しました．

「本件において，真に解決すべき事柄とは何なのか？」というのをもっと明確化すると，他の方からの回答に繋がるかと思います．

結局のところ，その明確化を（きっと他の方も）やろうとしてただけなのですが，迷惑/荒らし/etc と思われるのであれば通報等していただいて構いません．
→その場合，運営側が判定するでしょう．荒らしと判定されるならば私のアカウントが凍結されたりするはずです（過去にいくつもそうなった例があります）

[fana]

入れ違いになってしまったようなので最後に一つだけ：
一個前のコメントの末尾に　運営への通報　が可能である（ハズ）旨を追記しました．

[quickquip]

> DP表が動的計画法の全てという話でないかと思うので、動的計画法でとこうとしていないという話しではありません。
そうですね。表を考えるのが素直な問題を、なぜ表で考えようとしないのか? くらいの意図です。
どう解くかを知っているからこそ「表を考えるのが素直」となっているのは確かなのですが、しかし、とはいっても、初歩の段階の問題なので「なぜそんな遠回りをしよう(=まず表から考えない)としているのか?」というのも素直な感想です。

……なるほど。「また、直感的にdp表に起こす気にならない理由など思い当たる部分はありますか？」が質問の本丸なんでしょうか?

[quickquip]

Pythonのコード、「挫折した」コード=「動かない」コードなのか、「動いてちゃんと解ける」けれど「DPとは違うと思った」なのか、すぐ判別できなかったです。
（あとから聞こうと思ったけど書かなかったのです。質問の体裁として気になったので一応）

[u2025]

@quickquipさん
返信ありがとうございます。

Q. なぜそんな遠回りをしよう(=まず表から考えない)としているのか?
A. 超素直に端的にまとめると確かに以下のようにまとめられます。
「表を考えるのが素直ですが、直感的には別の方法で解けるのでは？というのがある」
で、実際にその方法で解くことも可能なわけです。
ご意見を頂いた上で考えてみると、もちろん複雑なアルゴリズム問題では直感的な方法でいくらやろうとしても解けないというケースがあって沼にはまるというのも「アルゴリズム問題を娯楽としてとらえると」醍醐味なところだろうというので、直感を信じるよりも表に起こすというセオリーを守るべきだというまっとうな考えもあるのかもしれません。

この感覚を疑問に感じている人がほかにもいるような感じですが、
例えば地図を見ていても実際の近道とナビゲーションのアナウンスが違った、何てことよくある話で近道(直感)の方がいいということは至極当然ありますよね。。。？
これがなぜこんなにも伝わらないのかというのが、わかっていません。

改めてご意見を頂くことで、私の中で言語化できなかった以上のことが分かりました。

Q. ……なるほど。「また、直感的にdp表に起こす気にならない理由など思い当たる部分はありますか？」が質問の本丸なんでしょうか?

DP表という与えられた公式のメカニズムを解くというのも一つ、もやもやではあるので本丸ではあります。
N * Mの表に関して言えば1つ1つ埋めていくということはもちろんわかりますが、この感覚を言葉で表現することが難しいので、経験者がどういう道を通ったのか？をモチベーション維持も含めて伺いたかったのです。
この気持ちってわかりませんか？

さっきから、ずっと他の人に「否定」ばかりされるので、素直な気持ちでコミュニケーションを取るのが少し怖いです。

[u2025]

> Pythonのコード、「挫折した」コード=「動かない」コードなのか、「動いてちゃんと解ける」けれど「DPとは違うと思った」なのか、すぐ判別できなかったです。
（あとから聞こうと思ったけど書かなかったのです。質問の体裁として気になったので一応）

ああ。これが完答なのかわからないという意見があるのですね。
質問時に想定していた回答者のレベルと実際の応対がマッチしていなかったので個々の説明は確かに改めてみると必要だと思いました。
質問文にある記載のコードは完全に正しく動作する完全な正解例です。
私の考えを皆さんに伝えるためにコードとして記載した次第です。

[quickquip]

とりあえず。「DP表」って正式な用語ではないかもしれないですが言わんとすることは分かります。質問に書くのに選択する言葉かという話だとしても「このくらい許されるだろ」と思います。というかむしろ「そこは分かれよ」くらいには思います。

> ああ。これが完答なのかわからないという意見があるのですね。
というよりは、見た段階の直感は「雰囲気は合ってそう」なのに、
> 最終的には、挫折したのですがイメージとしては
> (略)
> というものですが、いわゆるdp表といわれる A.size * Sの表を埋めていくものとは違っています。
と説明されていたので「どこか細部に駄目なところがある」のか? という印象でした。

質問自体は、ちょっと分からない感覚なので、すみませんが回答はないです。

[u2025]

@quickquipさん
すみません。ありがとうございます。
私も加担していますが、ここまで荒れて誰も回答しないでしょうからまた機を見てこのサイトを利用させていただければと思います。

ただ、逆に「皆さんはどのようなステップでDPを理解しましたか？」のような簡潔な質問ですと、逆のパターンで荒れる原因になるだろうという予測もたちます。
もしほかにここのを見ている方がいれば、質問方法のアドバイスも是非伺いたいものです。

個人的にアルゴリズムの勉強を順にやっていますが、数学の能力が低いのでわかる人にはぱっとわかる典型的な部分があり、言葉では説明し肉というのもあるのでしょう。
私のもやもやも言葉では説明しづらいので、特に「DP」が分かる方にご意見伺いたかったですが、そもそも質問サイトの選び間違いなのではないかという他の方の意見も筋が通っています。

私が難解ととらえた問題も、京大の友達なんかに質問するとさらっと解くので
何が難しいのか分からないというのがやっぱりほとんどの人が持っている感覚で、質問者側に降りてきてもらおうと思うのもかなり難しいものです。
そのため、簡単な意見でも励みになると考えていたものの、うまくいかないものですね。

お目汚し失礼致しいました。

Answer 1

まず、勘違いされているかもしれないので最初に説明しておくと、疑似コードとして挙げられていたアルゴリズムも、動的計画法の一種です。動的計画法の視点から見ると、一次元の配列を上書きすることで、二次元の表を使わずに済ませているだけで、やろうとしていることは同じです。

あとは、あえて二次元の表を使う意義が理解できれば、納得していただけるのではないかと思うので、いくつか理由を並べてみます。

更新の順番を気にする必要がない

一次元の配列で動的計画法の問題を解こうとする場合、計算の順番により必要な情報を上書きしてしまう可能性があるため、内側のループを前からにするか後からにするかを検討しないといけません。例えば、ご提示の疑似コードで、内側のループを先頭からにしてしまうと、正しい解が求められません。
二次元の表なら、必要な情報が上書きされる心配がないため、計算の順番を気にせず書けます。

どう頑張っても一次元だと解けない場合がある

一次元の配列をどのような順番で更新しても、必要な情報を上書きしてしまうような問題があります。例えば、こちらの問題と解説を参照してください。

問題
C - Vacation
解説
動的計画法超入門！ Educational DP Contest の A ～ E 問題の解説と類題集

具体的な組み合わせを求めることができる

例えば、部分和問題を一次元の配列で解いたとして、解が存在するかは分かりますが、具体的にどの組み合わせが条件を満たすのかを求めることはできません。
二次元の表であれば、こちらのリンク先にある手法を用いることで、具体的な組み合わせを求めることができます。

意外と解説がない！動的計画法で得た最適解を「復元」する一般的な方法

Comments

[u2025]

コメントありがとうございます。
ちゃんと問題を解けていないのですが二次元の表というのは問題としてはある種特殊な事例で、初心者向け問題で頻出するというだけで別にセオリーというわけでもなかったりするんでしょうか。と思いました。
全体的に自分の勉強不足な点があるので一度勉強しなおさないと、話の土俵にすら私立てていないですね。
と、以下の文章を書いているうちに思いました。

言葉で言い表しづらいのでどうしても「直感的」という言葉を使ってしまうのですが、
夏休みの問題に関して、ちゃんと解いていませんが三つ分の配列を作って二つを比較する方が直感的？に考えてしまいました。もちろんそれを二次元の配列に置き換えることは当然ながら可能ですし、要素が多くなるとそうせざるを得ないのですが、この時に考える二次元の表のイメージが私の持っているそもそものイメージと若干異なり、勉強不足を感じました。
ただ、うだうだ言っても仕方ないので勉強あるのみですね。ありがとうございます。

「復元」の方法についても以前、あるデータの組み合わせでNと一致する組み合わせのパターンを複数知りたい。見たいなときに通ったのですがあまり記憶に残っていないので再勉強して、二次元表の必要性を自分の中でも考えてみようと思います。

今回質問してみて、DPの二次元の表が直感と違うという意見があまりなく私個人が持っている特殊な事例と知れただけでも十分な収穫です。。。

ご回答ありがとうございます。

(そもそも、DPの複雑な、値、前回の値、キーみたいなのを組み合わせることでさえ脳のキャパオーバーなので、DP表の全体を瞬時にイメージするというのがキャパオーバーで、1個前の要素やそこに飛び移れる要素、しか考慮できないのが問題なのかもしれないですね。。)

> 例えば、ご提示の疑似コードで、内側のループを先頭からにしてしまうと、正しい解が求められません。

これは問題
(3) コイン問題（最小枚数）
の問題ではそうなのですが、上向きに行けば同じのに出くわすって感じなのは自分的にはすんなりと受け入れられ足りしました。(てか、この問題も不完全ですね。AIに出題してもらった時も不完全だったので、ちゃんと何回でも選べる旨は書き足さないとですね。そもそも問題文読んでる方がここにいないと思うので、細かい部分ですが)
というかそもそもとして、二次元配列で解く方法を復習しないと話の土俵にも立ってないですね私。

[actorbug]

論点がボケるのであえて回答には書かなかったのですが、ご提示の疑似コードは「配るDP」で、一般のDPのコードでよく使われるのが「貰うDP」という違いはあります。両者が異なって見えるのは、このあたりが原因かもしれません。

[u2025]

> ご提示の疑似コードは「配るDP」で、一般のDPのコードでよく使われるのが「貰うDP」という違いはあります。

え！すごい！超すっきりしました
ありがとうございます
改めてアルゴリズムをそう考えてみるとすっきりしました！
納得できました！ありがとうございます

AIにこの回答貰うのは至難ですね。人間に聞けて良かったです！

Answer 2

意味不明な荒らされ方をされるので質問を閉じます。
コミュニケーションにおいて、世間一般で使われる用語を用いるのは当たり前だと思います。
「動的計画法」という大層な名前を使う意味がわからないという指摘がありますが、コミュニケーションを円滑に進めるために、「言葉」を使うのは当たり前です。
もしそれが一般的な場所であれば「動的計画法」は「専門用語」なので、一般に通づると考え使用するのは不適切かもしれません。
このサイトはそうではなく、専門的な場所なので専門用語に文句を言う惨状は異常です。

Comments

[fiveHundred]

> このサイトはそうではなく、専門的な場所なので専門用語に文句を言う惨状は異常です。

こういうケースの場合、大体その専門用語は

- 勝手にあなたが作っている
- 意味が間違っている

ということです。
そういうのは通じないのは当然です。

あなたの質問の場合、そもそも「背景が分からない」「分からない点が分からない」など他の回答者には全く通じないような内容です。
むしろ、通じていないのに回答を頑張っている回答者に感謝すべきです。
もしそのつもりが無いのであれば、立派な迷惑行為なのでこのサイトから去ってください。
「荒らしている」は勝手にあなたがそう思っているだけです。

[u2025]

「背景が分からない」「分からない点が分からない」など一度もそのような返信は来ていません。
いわれなければこちらも分かりませんよ？
感謝すべきはあなたの勝手な思想です。であれば、私にも感謝すればいいじゃないですか。精一杯質問に答えていますよ。

あなたは今、何のために私に返信しているのですか？

[fiveHundred]

善意で回答を頑張っている回答者に対して、なぜか攻撃していたので、反論しただけです。

[meg_]

もしかしてu2025さんはすごく頭の良い人ですか？動的計画法は数式を見れば分かる、または数式も見なくても問題設定から自然に解法を導き出せる人でしょうか？だからわざわざ表に起こすなんて意味ワカラン！ってことですか？そうだとすると皆さんのコメントを「関係ない話を延々とし続ける」と思うのも自然なことかもしれませんね。「細かいところが気になりすぎて」も参考書がU2025さんには冗長なんだと思います。

[u2025]

@fiveHundred

申し訳ないのですが、何が善意なのか毛頭分かりませんでした。
何が善意なんでしょうか？
私の観点として一人に対しては連投は迷惑行為ですし、
もう一人に対しては

> 私には解にたどり着けない方法を正しいと思うことが理解できません。挫折→回答に納得、も飛躍していて理解できません。すみませんがここで失礼します。

も失礼な発言かと思います。
少なくとも丁寧に返信している人に対してこの発言が出るのはおかしいかと思いますけど。
というか、動的計画法の質問をしているのに同的計画法を知らない人が返信してくること自体迷惑だと思うのですけど。

Answer 3

(1)皆さんがdpを学習したときの方法について
(2)直感が大事か？dp表も大事か？皆さんがアルゴリズムの発想をする際にイメージするのはなにか？

「dpを学習」とかいうことをしたことがありません．

というか， 実際に直面した問題 の解法について考える際に「これ何度も同じ計算するの無駄すぎね？　計算量と記憶容量のトレードオフで処理時間を減らす方向で…」みたいなのは 当たり前に/自然に 考えることであり，
そんな程度の話にいちいち「DP」とか何とかいう，なんだかかっこいい名前を付けて呼ぶような話とも思えません．

問題を小さくわける/再帰/結果を配列にいれとく/etc みたいなのはプログラムを書いて何かをしている人であれば誰でも日常的にやっている程度の話ではないのでしょうか？

(3)どういった形式の問題なら直感とdp表のギャップを埋められるか？また何故このような思考の違いがでるのか？

そもそも今回の状況について言えば， 実際の問題に直面するよりも前の段階で あなたの中に
【「DPというのはこういうものである」という何らかのイメージができていて，且つ，これから出題される問題はとにかく何が何でもそれを用いて解かねばならない】
とかいう謎の前提が存在していることが「違い」の原因です．
普通，解決すべき課題が何なのかがわからない時点で「次に直面する問題はこのアルゴリズムで～」とか考えるわけないですよね．

実際に何かしらの初見の問題に対面した際に複数個の方法論が思いつくというのはよくあることなわけで，
それらの方法の間に「ギャップ/違い」があるのは，何をどう考えても 当たり前のこと です．
（差が無いなら，異なる方法ではないのだし，その差を「埋める」ことに何の 意味/意義 があるというのか？）
その場の制約等々に応じて，複数の候補の中から必要十分な方法を選べば良いだけのことです．

が，本件について言えば，そもそもが「ＤＰの学習」なので，上記の「謎の前提」に従う以外に道は無いハズです．
行動の目的自体が「ＤＰ」なのですから，あなたが直感的に思いつく方法が「ＤＰではない」場合，それは無視するしかないです．
「納得」を後回しにするということは，「ＤＰの学習」自体を後回しにするということと同義かと思えます．

---

[追記]

問題1~3にあなたならどう回答するか、どういう方針で取り組むのかを答えてくださった方が、有意義だと考えてしまいます。

こんな…かなぁ…？
簡単な入力例でしか確認してないのでコレで合ってるかどうかは保証しかねますが，「方針」はコメントとして記しておきました．

//MEMO :
//* 扱う値が正の整数ならば unsigned とかにすべきかもしれませんが，
//  ここではとりあえず方針を示すのが目的なので，全部 int で書いてます．
//* 途中経過の情報を記録する配列は全て Memo という変数名にしています．

//(1)
//N個の正の整数 a_1, a_2, ..., a_N が与えられます。
//これらのうちいくつかを選んで、ちょうど合計 S にできるか判定してください。
template< int S, int N >
bool Q1(
    const int (&A)[N]   //N個の正の整数
)
{
    //Memo[x] は，処理中に合計値xになったか否か
    bool Memo[S + 1];
    for( bool &b : Memo )b = false;
    Memo[0] = true;

    //{ a_1 } だけで達成できる合計値とはどれどれか？
    //{ a_1, a_2 } だけで達成できる合計値とはどれどれか？
    //…
    //と見ていく感じで Memo を更新していく．
    //（質問文で示されている疑似コードと全く同じかと）
    for( int a : A )
    {
        for( int x=S-a; x>=0; --x )
        {
            if( Memo[x] )
            {   Memo[x+a] = true;   }
        }
    }

    return Memo[S];
}

//(2)
//N段の階段があります。
//一度に1段か2段ずつ上ることができます。
//N段目に到達する方法は何通りあるか求めてください。
template< int N >
int Q2()
{
    //Memo[x] は，x段目に到達できる方法の数
    int Memo[ N+1 ] = { 0 };
    Memo[0] = 1;

    //単に，下の段から順にパターン数を積み上げていくだけでいけるんじゃないかな
    for( int x=0; x<=N-2; ++x )
    {
        Memo[x+1] += Memo[x];
        Memo[x+2] += Memo[x];
    }
    Memo[N] += Memo[N-1];

    return Memo[N];
}

//(3)
//N種類のコインがあります。
//それぞれのコインの価値は coins = [c1, c2, ..., cN] です。
//合計金額 M を作るときに必要なコインの枚数の最小値を求めてください。
//作れない場合は -1 を返してください。
template< int M, int N >
int Q3( const int (&C)[N] )
{
    //Memo[x] は，x円を作るのに必要なコインの最小枚数．
    //ただし「x円を作れない」ことを示す特殊値として -1 を用いる．
    int Memo[M+1];
    for( auto &m : Memo )m=-1;
    Memo[0] = 0;

    //金額が低い側から順に作れるかどうか見ていく
    for( int iFrom=0; iFrom<M; ++iFrom )
    {
        if( Memo[iFrom]<0 )continue;

        //iFrom円を作れるなら，それに１枚コインを足した金額は全て作れる
        for( int c : C )
        {
            int iTo = iFrom + c;
            if( iTo > M )continue;
            //iTo円を作るのに要する最小枚数を更新
            if(
                ( Memo[iTo]<0 ) ||
                ( Memo[iTo] > Memo[iFrom]+1 )
            )
            {   Memo[iTo] = Memo[iFrom]+1;  }
        }
    }

    return Memo[M];
}

Comments

[fana]

まぁ， "AtCoder" なんて語が見えている場面において，こんな話しても意味ないのかもしれないけど．

そっち系に特化した話なのであれば，　ひたすらそっち系の問題を解いて慣れる　しかないんじゃない？

[u2025]

私がしたいのは実際に起きた問題の解決ではなくアルゴリズムの勉強です。
実務においてそう高負荷になるような実際の問題に直面するのは稀ですし、学習コストが馬鹿にならないので特定の問題を「アルゴリズム」の問題としてとらえることはほとんどありません。

重箱の隅をつついても仕方がないので、
であれば、私の記載した問題1~3にあなたならどう回答するか、どういう方針で取り組むのかを答えてくださった方が、有意義だと考えてしまいます。
この意見に間違いがあればご返信ください。
その他に意見があればご返信させていただければと思います。

1~3の解き方を見せてくれるのであれば回答文を編集し追記していただけると助かります。
(当然、dpなどという大層な名前を付ける必要はありません。)

ご協力ありがとうございます。
お手数をおかけしますがよろしくお願いいたします。

私の返信に納得できなければ、改めて1文1文に対してご返信させていただきます。
答えてほしい疑問がございましたらお手数おかけしますが改めて記載していただきたいです。
今のところでは私はあなたの回答がずれていると思いますが、返信する意義があるのか不明なため一つ一つは書きません。