質問編集履歴
1
コメント欄が煩雑なため質問文に転記
title
CHANGED
|
File without changes
|
body
CHANGED
|
@@ -71,3 +71,27 @@
|
|
|
71
71
|
|
|
72
72
|
### 補足情報（FW/ツールのバージョンなど）
|
|
73
73
|
最終的にはAtCoderを使用して問題を解けるか、すっきりするかをテストしていきたいと考えています。
|
|
74
|
+
|
|
75
|
+
|
|
76
|
+
### コメント返信を転記
|
|
77
|
+
Q. ｢挫折した｣のにそのイメージに拘る理由は何でしょうか？そこが｢納得感｣とやらに関連している気がするのですが。
|
|
78
|
+
A. 挫折したのにイメージにこだわる理由は、回答に納得できるからです。
|
|
79
|
+
何といえばわかりやすいのか分かりませんが、Aの道とBの道を選んで、Aの道の通り方が一切わからない、Bの道の通り方はなんとなくイメージはつかめている、Bの道を最後まで行けなくとも、答えだけ見るとBの方が納得できた。そういうことです。
|
|
80
|
+
dp表の方は頭の中で現状勉強不足なのも含めて再現できないので、先のコメントと少しかぶるのですが、直感的なやり方で解決できるのであればセオリーにこだわらなくてよいのか？というのは疑問です。応用で使うのであれば結局そこでは納得感は生まれるはずなので、興味関心も含めて意見を伺いたいです。
|
|
81
|
+
|
|
82
|
+
Q. 質問記載のdp表の意味が分からない
|
|
83
|
+
A. 私の方でもdp表のアルゴリズムに納得、理解していないので説明させるのは酷だと思いますが動的計画法は全探索すると組み合わせ爆発が起きる問題において、任意の計算結果を求めるのに、ステップごとに分けることで、N ＊ Mの範囲に収めることができるアルゴリズムです。
|
|
84
|
+
数列がa_1, a_2, a_nとあって、その組み合わせで合計Mを作れるか？という問題においては、
|
|
85
|
+
a_1, a_2の列、合計0..Mの行からなる表を作成し埋めていくことで、N列M行を見れば最終的な結果が分かるというアルゴリズムになります。(行列は転置してもいいと思いますが、どっちがセオリーかはよく知りません。)
|
|
86
|
+
これは要するに二次元配列にマッピングし逐次的にマスを埋めるアルゴリズムをプログラム的には書くことができます。
|
|
87
|
+
私が質問文に書いた(1)の解法としてもこれはdpと呼べると思います。
|
|
88
|
+
よく考えたらこの解き方自体、別の問題の派生でその時に動的計画法という言葉を知らなかったのでこの書き方を発想してしまうのかもしれません。
|
|
89
|
+
皆さんはアルゴリズムの勉強か何かで配列のインデックスの方を着目して、要素を埋めるという解法を通っていない、つまり一般的な方法ではないという形になるのでしょうか。C言語を学んでいるときに通ったのですが。
|
|
90
|
+
|
|
91
|
+
### コメント返信時の補足
|
|
92
|
+
後出しで申し訳ないのですが、問題を説明しているサイトを見るとか、本を見るという点においてですが、著者が天才なのか自分が数学の教養がないのか細かいところが気になりすぎて、どうしても牛歩になってしまいます。
|
|
93
|
+
アルゴリズムの問題ですので実際にプログラムを書かなくても、勉強はできるはず。。。と思いGPTに先生をやってもらっていますが、結局問題を解こうとするうちにやる気が上がってPCを開いてしまいます。
|
|
94
|
+
でも、この勉強法でも今のところいいと思っています。少なくとも前に進んでいる感覚があるので。
|
|
95
|
+
|
|
96
|
+
|
|
97
|
+
よろしくお願いいたします。
|