実現したいこと
動的計画法(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を開いてしまいます。
でも、この勉強法でも今のところいいと思っています。少なくとも前に進んでいる感覚があるので。
よろしくお願いいたします。

回答3件
あなたの回答
tips
プレビュー