私は現在動的計画法を学んでおり、理論はよく知っていますが、新しい問題に対する DP アルゴリズムの設計は依然として困難です。
これは私が今本当に欲しいものです-動的プログラミングによって解決できる問題を提起する本またはウェブサイト。また、説明付きの解決策もあります。数時間頭を悩ませた後でも問題を解決できないかどうかを確認したいと思います。グラフアルゴリズム、動的プログラミングなど、いくつかのカテゴリのアルゴリズムにこの種のものを提供するリソースはありますか?
PS私はTopcoderを検討しましたが、そこにあるソリューションは、効率的なソリューションを実装することを学ぶのにはあまり適していません.
ACM コンテストの問題セットはどれもうまくいくでしょう。そのようなものを見つけるためのいくつかの場所:
TopCoderのソリューションが優れた実践例ではないことに、私は多少同意しません。上位ユーザーが提出したソリューションは、多くの場合非常に単純であり、必ずしも非常に効率的であるとは限りませんが、十分に効率的です。本当に重要なことは、コードが非常に短いことです。これにより、特に解決策をまだ知らない場合は、理解しやすくなります。
通常のプログラムを同じスタイルで書くことはお勧めしませんが、オーバーエンジニアリングについて何かを教えてくれることは間違いありません。カスタム イテレータ、コンパレータなどを使用した Java のソリューションを見たことがありますが、アルゴリズム自体は些細なものであったとしても、それらを理解するのははるかに困難でした。
以前、Paul Grahamのエッセイを読んだことがあります。彼は、トークンの少ないプログラムの方が理解しやすいと述べています。TopCoder は、少なくとも一部のドメインでは、これが真実であると私に確信させました。
Project Eulerの多くの問題は、動的計画法を使用してエレガントに解決できます。
http://www.topcoder.com
ここでは、さまざまな難易度のすべてのタイプの問題を見つけることができます。