5

明日は、オンラインのGoogleテストを新しいものとして作成します。どうやら、彼らは間違いなく動的計画法に関する1つの問題を尋ねていますか？

解決策とともにCのDP問題を収集するための優れたリソースを知っている人はいますか？私はDPが何であるかを知っており、1、2回使用したことがあります。ただし、テストでDPの問題を解決するように感じますが、一般的な問題を事前に実践しておくと、アプローチが容易になります。

Cのソリューションに関する優れたリソースや問題セットは高く評価されます。ありがとう。

4

4 に答える 4

8

さて、これらのリンクはすべて私が個人サイトに投稿したコードスニペットへのリンクであるため、これが「恥知らずな自己宣伝」としてカウントされないことを本当に望んでいます。これが不適切な場合は、お知らせください。削除させていただきます。

かなり古典的ないくつかの楽しいDPの問題があります：

  1. 最小編集距離：2つの文字列AとBが与えられた場合、AをBに変換するために必要な編集（挿入、削除、または置換）の最短数を見つけます。これはレーベンシュタイン距離と呼ばれます。 （私の解決策）
  2. 最適なシーケンスアラインメント：2つの文字列AとBが与えられた場合、AとBをアラインメントするためにシーケンスに挿入する必要のあるギャップの最小数を見つけます。これはNeedleman-Wunschアルゴリズムと呼ばれます。（私の解決策）
  3. 単一ソースの最短経路：有向グラフGと単一ノードsが与えられた場合、エッジが正または負になる可能性があるがサイクルが存在しないと仮定して、グラフ内のsから他の各ノードまでの最短経路の長さを見つけます。これはベルマンフォードアルゴリズムです。（私の解決策）
  4. すべてのペアの最短経路：有向グラフGが与えられた場合、ノードのすべてのペア間の最小距離を見つけます。これはFloyd-Warshallアルゴリズムです。（私の解決策）

うまくいけば、これはやや有用であり、明日は幸運を祈ります！

于 2011-01-09T08:38:27.540 に答える
1

練習するには、SPOJ で利用可能な問題の 1 つを取ることができます。DP のものを簡単に認識するために、 Problems Classifier (キーワード: dp)で確認できます。

于 2011-01-09T12:22:14.497 に答える
1

TopcoderのWeb サイトは素晴らしいです。すべての問題で DP が使用されているわけではありませんが、多くの問題で DP が使用されています。3 つの異なる難易度の過去の大会のすべての問題に無料でアクセスでき、問題作成者によるすべての問題の試合後の説明も利用できます。それだけでなく、コンペティションに参加しているコーダーが提出したソース コード ソリューションをすばやく掘り下げることができます。

しばらくそこに戻っていませんが、少なくとも C++、Java、C# が許可されており、現在は他のいくつかの言語を信じています。

于 2011-01-09T09:28:10.767 に答える
1

「バイオインフォマティクスアルゴリズムの紹介」という本を集めることをお勧めします。これにはDPに関する完全な章があります.@templatetypedefが言及したように、最小編集距離、最適な配列アラインメントには他の問題があります。自分でそれをしなければなりませんが、それらを読むとかなり面白いことがわかります。

于 2011-01-09T10:37:42.057 に答える