php - 動的計画法の状態を保存するアルゴリズム

Question

これは、動的計画法を使用した問題の状態の保存に関する質問です。

• DP のすべての問題は結果を保存し、それらをさらに使用して計算を削減します。たとえば、関数値を計算f(x,y)=290し、それを 2 次元配列 $save に保存するとし$save[x][y]=290ます。これは'f'、 が少数の変数に依存している場合に実行できます (例: 上記の例では x と y の 2 つの変数のみ)。しかし、たとえば 10 個または 15 個の変数に依存している場合に何ができるか。'f'10 次元または 15 次元の配列を作成すると、メモリ効率が低下します。

• 別の解決策として、変数の値を連結し(一意であると仮定)、連結によって得られた文字列をキーとして使用して、それらを連想配列に格納することができます。ただし、連結は時間のかかる操作です。したがって、メモリと時間の間にはトレードオフがあります。

状態が依存する変数の数が多い場合、状態を保存する方法はありますか? OOPS やポインターを使用する方法があると思いますが、何かをフレーム化することはできません。助言がありますか？すべてのアイデアを歓迎しますが、 'C'または'PHP'を念頭に置いたソリューションが優先されます。「C」が連想配列を処理しないことは知っていますが、状態を保存するアルゴリズム/方法が必要なだけです。

Answer 1

1. まばらなデータに状態を保存することは、一般的にmap (連想配列)インターフェイスを使用して行われます。Cには組み込まれていませんが、インターネットにはこの機能を提供するライブラリがたくさんあります。

2. とにかくほとんど/すべての (x1,...,xk) 値を計算する場合 - a の使用mapはお勧めしません - 遅くなり、メモリを節約しません (実際には、これらのケースでは逆です)。この場合、おそらく多次元配列が最適なソリューションです。

3. DP では多くの場合、これまでのすべての情報の配列は必要なく、以前に計算された「行」だけが必要であり、配列をオーバーライドします。効果的に - k*N テーブルを必要とする多くの DP 問題では、実際にはサイズ 2*N のテーブルのみが必要であり、同じ行を繰り返しオーバーライドします。すべてのデータではなく、前の行のデータだけが必要な場合、同じ原則が私が信じているどのディメンションにも当てはまります。