熊崎 宏樹:まず、本気で競技プログラミングに取り組んでいる人からしても自明ではないのでわざわざ専用の練習コンテストが開かれるほどのトピックであるという前提は共有されているかと思います。 Educational DP Contest / DP まとめコンテスト 世の中にある参考書を眺めると「問題を部分問題に分割できること」「部分問題の答えを再利用できること」「問題サイズが極端に小さい場合の答えが簡単であること」などよく言われます。1次元のDPならまだしも世の中の2次元・3次元のDPに更に期待値の計算が加わったりすると何を軸に取るか考えるだけでも一苦労です。つまり自明ではありません。いっぱいDP問題を解いて類型を覚えていくぐらいしか確実に言えるアドバイスはありません。 という答えまでは流行りのChatAIに聞いても返ってくるので、少し人間らしい答えをするとルールや評価ロジックの観点から少しだけ攻略ができます。 ・DPに使うテーブルのサイズはまず10^9を超えません。巨大なテーブルを用意するだけでも言語によってはエラーが起きかねないし「特定の言語では絶対に解けない問題」を問題作成者は基本的に避けます。逆に言うと10^6ぐらいの制限が出てきたらDPが示唆されている可能性があります。 ・一般論として採用時のコーディング面接でDPはあまり好まれません。何故なら典型になるか複雑で手が出せないかのどちらかになりがちだからです。DPに思い当たった時点で部分点、何をテーブルに置くか方針が決まったら部分点、最後まで書けたら満点、みたいな粗い目盛りの定規で候補者を測る事になってしまい「対話的に協力しながら答えを探る」という実際の仕事のシミュレーションとして理想的とは言えません。 参考になれば幸いです。