問題タブ [bottom-up]

古典的な階段問題を考えると、「デイビスは家にたくさんの階段があり、各階段を一度に 1、2、または 3 段ずつ登るのが好きです。非常に早熟な子供であるため、彼は階段に到達する方法がいくつあるのか疑問に思っています。階段の上。」

私のアプローチは、再帰を伴うメモ化を次のように使用することです

私の頭に浮かぶ質問は、このソリューションがボトムアップかトップダウンかということです。私のアプローチ方法は、上位の N 値を計算するためにずっと下に行くためです (再帰ツリーを想像してください)。私はこれをボトムアップと考えています。これは正しいです？

長さ n インチの棒が与えられます。整数の長さのさまざまな部分に切り取ることができます。あなたの目標は、可能なすべての部分の長さの積を最大にすることです。少なくとも 1 つのカットを作成する必要があります。ロープの長さは 2 メートル以上と仮定します。参考：https ://www.geeksforgeeks.org/maximum-product-cutting-dp-36/

その他の参考文献:ロッドをカットして利益を最大化するためのアルゴリズム

2Dテーブルを使用したボトムアップの動的計画法を使用して、この質問を行いたいです。

長さが 5 であるとします。

各セルは、特定の長さのロッドで指定されたカット数で得られる最大製品と、カット後に残った最大長を示します。

たとえば、セルにカット数 2 とロッドの長さ 4 を入力する必要があるとします。各セルには、特定の長さの最大製品を格納するだけでなく、カット後に残った最大の長さも格納すると仮定します。

長さ 4 を 1 回カットした後、左部分を 2 に、右部分を 2 にカットするため、最大積は 4 になります。最大積の 4 と最大部分の 2 の 2 つの数値を保存します。セル (2, 4) にいるときは、カットできるかできないかのどちらかです。カットを行わない場合は、現在の行を調べます。そして、それぞれの長さをループします。この場合、長さ 2 と長さ 3 をループします。長さが 2 の場合は、残りの 4-2=2 があり、乗算して 4 を取得します。次に、残りの長さを取得するために 3 で同じことを行います。を 1 にして、これに 2 を掛けると 2 になります。

もう 1 つのオプションは、カットを行うことです。次に、上の行を確認する必要があります。また、その行の先頭からループします。次に、最大値を選択します。

私の問題は、すべての列をループするたびに、つまり左から現在のセルまでループする必要があることです。これにより、時間の複雑さが O(n^3) になります。

2D テーブルを使用する代わりに O(n^2) でこれを行う方法はありますか?

自社のBIシステムをゼロから開発しており、現在はデータウェアハウスの設計を行っています。全くの初心者で分からない事が多々ありますので、今後ともよろしくお願い致します。

私の問題は次のとおりです。

1) ソース システムには、「Booking」および「BookingAccess」というテーブルがあります。予約テーブルには、チェックイン時間とチェックアウト時間、予約日、予約番号、その予約の総額などの予約のデータが保持されます。

一方、BookingAccess では、bookerID、customerID、processID、hotelID、paymentproviderID、およびその予約の現在のステータスなど、予約に関連する外部キーを保持します。Booking と BookingAccess は 1 対 1 の関係にあります。

私たちのソース システムは、これらの予約の有効性を確認するためのものであり、これらの予約は私たちのものではありません。これらの予約情報は他のソースから受け取り、上記のプロセスを外部委託します。総額は、当社が検証する必要がある予約の単なる情報であり、当社のビジネスの一部ではありません。BookingAccess テーブルに保持されている予約の現在のステータスは、システム内のその予約の現在のステータスであり、「処理中」または「完了」のいずれかになります。

Ralph Kimball から読んだことによると、この状況では、「Booking」はディメンション テーブルであり、BookingAccess は事実である必要があります。BookingAccessは、予約が「処理中」のときと予約が「完了」のときを追跡する必要がある[累積スナップショットテーブル]のようなものだと思います。

私はそれを正しく理解していますか？

2) "Booking" テーブルには、"ImportID" という外部キーもあります。このキーは、「インポート」というテーブルにリンクしています。この「インポート」テーブルには、ファイル名、インポートされた日付、インポートされた合計予約などの属性を含む、システムにインポートされたファイル (これらのファイルには「予約」テーブルに書き込まれる予約が含まれています) の履歴レコードが保持されます...

私の観点からは、これは明らかにファクト テーブルです。

しかし問題は、"Import" テーブルと "Booking" テーブルが 1 対多の関係にあることです ("Import" テーブルの 1 つの ImportID は、"Booking" テーブルで同じ ImportID を持つ 1 つ、2 つ、またはそれ以上のレコードを持つことができます)。 ）。これは、Fact と Dimension の関係は多対 1 でなければならないというファクト テーブルの考え方に反するものであり、事実は常に多側にあります。

では、このケースを解決するにはどのようなアプローチを使用すればよいでしょうか? この問題を解決するためにブリッジテーブルを使用することを考えています。ただし、「インポート」テーブルには多くのレコードがあるため、これが良い方法かどうかはわかりません。そのため、これらすべてをカバーするためだけに大きなブリッジ テーブルを作成する必要があります。

3) リレーションシップと情報が混在するテーブル (ソース システムから) を、リレーションシップのみを含むファクト テーブルと情報のみを含むディメンション テーブルに分離する必要がありますか? (たとえば、ソース システムの「Customer」というテーブル。このテーブルには、顧客名、顧客住所、顧客タイプ ID、顧客の親 ID などの情報が含まれています。)

BI ツールを使用して物事を分析する場合 (たとえば、customertypeid = 1 を持つ顧客の数を分析する場合)、ファクト テーブルが含まれていないと何かおかしいと感じるので、この質問をしています。

それとも、単なるディメンション テーブルとして扱い、snowflake-schema を使用する必要がありますか? しかし、これにより、データ ウェアハウスでスター スキーマとスノーフレーク スキーマが混在することになります。これは正常ですか？私は、スノーフレークスキーマをできるだけ使用したり混ぜたりすることを避けるべきであると述べているいくつかの公式情報源 (おそらく Oracle) を読みました。しかし、Microsoft などの一部の情報源は、これはごく普通のことだと言っています。Advanture Work Data Warehouse サンプル データベースでさえ、この種のアプローチを使用しています。

または、その「顧客」テーブルのすべての関係を非正規化する必要がありますか? しかし、Customer に多くの列が含まれるようになり、"DIM_Customer" テーブルのすべての行の履歴を追跡するのが非常に難しくなるため、これは良いアプローチではないと思います。たとえば、「Customer」テーブルのいずれかのリレーションに変更が発生した場合、「DIM_Customer」テーブル全体を更新する必要があります。

データ ウェアハウスに関しては、まだ多くの質問があります。私は、助けやコンサルタントなしで、ほぼ一人で作業しています。そのため、何か不都合や間違いがあった場合はご容赦ください。

動的計画法を使用して古典的なパーティションの問題を解決する必要があります。入力として正の整数の配列があり、nは整数の数、sはそれらの整数の合計です。入力の要素を使用して構築できる 2 つのセット間の最小差を見つける必要があります。入力配列と同じサイズの「所有権」と呼ばれるブール配列も出​​力する必要があります。これは、要素が最初または 2 番目の最適なセットに属しているかどうかの情報を提供します。たとえば、所有権配列のi 番目の値が true の場合、入力配列のi 番目の要素は最初のセットに属します。

私のプログラムは、ボトムアップ アプローチを使用して最小の差を見つけます。このタスクでは、プログラムのメモリの複雑さがθ ( s ) である必要があるため、従来のアプローチのようにサイズ n*s の 2D 配列を使用する代わりに、その配列の 2 行のみを使用しています。最初の行では、以前に処理された行を保持するため、前のソリューションに基づいて 2 番目の行を埋めることができます。

問題は、このメモリの最適化では、所有権配列をどのように埋める必要があるのか​​ わからないことです。

n*s 配列でバックトラッキングを使用してセット要素を取得できることはわかっています。ただし、タスクの制約により、その方法を使用できず、所有権テーブルを効率的に作成する方法がわかりません。

ボトムアップ アプローチ でメモリの複雑さθ ( s ) と時間の複雑さO (n*s) の制約を使用して、どの要素がこれら 2 つの最適なセットのどちらに属しているかを効率的に見つける方法はありますか?

C# での私の現在のコード: