dynamic-programming

4熱

2答えて

なぜメモ変換はマージソートの実行時間を改善しないのですか？私はこの課題を割り当てタスクから持っています。しかし、私が知る限り、Merge Sortは分裂と征服のアプローチ（重複する部分問題なし）を使用しますが、Memoizationは動的なプログラミングに基づいています（重複した部分問題あり）。私はマージソートの実行時間がO（nlogn）であることを知っています。私はウェブ検索エンジンでも検索

0熱

1答えて

LeetCodeハウス・ロバー・パス

私はリートコードハウス・ロバーの問題1を解決しましたが、パスを印刷できませんでした。私はリストを使用していくつかのトリックを試みたが、常に間違った答えを得る。どのように私は以前の決定を覚えて、要素を削除し、要素をリストに追加して住宅リストを持たせることができますか？ public static int rob(int[] nums) { if (nums == null || nums.

0熱

1答えて

ハスケルでの相互再帰のためのMonad.Memoのメモ帳

私はHaskellでいくつかの動的再帰実装を行っています。私はメモを使って物事をスピードアップすることに決めました。 Monad.Memoは、正確なケースのMemoTトランスを提供しています。しかし、格納された値の内部表現としてMapを使用します。そして、これは私に大きさのスピードブーストを与えましたが、まだ十分ではありません。 libは内部ストレージとしての配列ベースおよびベクトルベースの実装

3熱

1答えて

0-1回のナップザックの回数の組み合わせ

合計がいくつかの制限よりも小さいか等しい場合、最も効率的（時間とメモリ）の方法でサブセットの数を数えられるのでしょうか。例えば、セット{1, 2, 4}と制限3の場合、そのような数字は4（サブセットは{}, {1}, {2}, {1, 2}です）です。私は、ビット・ベクトル（マスク）でサブセットを符号化し、以下の方法（擬似コード）に答えを見つけることを試みた： solve(mask, sum, l

1熱

2答えて

バーコードが制限付きで表示される可能性のある方法の数

これは私が持っているグレーダーの宿題の1つです。私は今この質問を2日間苦労してきました。トピックはダイナミックプログラミングに関するもので、私はそれをどのように理解するか分かりません。詳細は次のとおりです。バーコードは、異なる配置の黒と白の縦線で構成されています。簡単にするために、バーコードを識別するために "0"と "1"の文字列を使用し、 "0"は黒線を表し、 "1"は白線を表します。バ

0熱

1答えて

任意のギャップペナルティを伴う配列アライメント

私は最適な方法で2つのDNA配列をアライメントしたいと思っていますが、Lが3の倍数であればペナルティはある定数a。 Lが3の倍数でない場合、ペナルティはいくつかの定数bに対してb * Lです。私はO（n * m）アルゴリズムを設計することになっています。ここで、nとmは最適な配列を見つけるDNA配列の長さです。しかし、これについての難しい部分は、私が拡大しているギャップの大きさを把握しなければな

0熱

1答えて

最小コストのための最適なグリッドパスの記録

したがって、私は2次元マトリックスを持ち、最小コストを与えるパスを記録することになっています。私は下にまたは右に移動することができます。例： 2 4 1 3 7 6 3 8 9 Output: right right down down 私のコードは、間違った答えを与えますが、私はなぜそれを見つけることができません。以下のコードを添付しました。 public static List<S

0熱

1答えて

グラフ理論、与えられた距離を持つすべてのパス

私は、旅行者がある距離をグラフで移動でき、すべての双方向エッジがある長さ（距離）を持つ問題を発見しました。特定のエッジ（いずれかの方向）を走行すると、あなたはあなたが旅行することができます与えられた距離のために収集することができる最大のお金を見つける必要があるので、いくつかのお金/ギフト（それはすべてのエッジのために問題になっている）を得ると仮定する。基本的な問題は、与えられた距離（グラフ内にルー

0熱

2答えて

このようなDPアレイの初期化の理由

LeetCode.comからa questionを解決しています。質問は次のようなものです：あなたは通りに沿って家を奪うためにプロの強盗を計画しています。それぞれの家には一定の金額が隠されています。隣接する家にはセキュリティシステムが接続されており、隣の2つの家が同じ夜に壊れた場合、自動的に警察に連絡します。各家の金額を表す負でない整数のリストが与えられている場合、警察に警告することなく、今夜

1熱

1答えて

NZECエラーが

私はSPOJ.ItのACODE問題を解決していますが、単純なDpの問題here あるspojこれは私のソリューションです： //http://www.spoj.com/problems/ACODE/ import java.util.Scanner; //import java.util.Math; public class Acode { public static void