1

私は次の再帰関数を持っています：

typedef unsigned long long ull;

ull calc(ull b, ull e)
{
  if (!b) return e;
  if (!e) return b;
  return calc(b - 1, e - 1) + calc(b - 1, e) - calc(b, e - 1);
}

動的計画法（つまり、ストレージを使用）で実装したいと思います。使ってみましたmap<pair<ull, ull>, ull>が、遅すぎます。配列を使って実装することもできませんでしO(1)た。

b, eこの関数が大きなsをすばやく解決できるように解決策を見つけたいと思います。

4

4 に答える 4

5

テーブルb/eを作成し、セルごとに入力します。これは、空間と時間の複雑さがO（MaxB * MaxE）のDPです。

コメントのAnteの提案により、スペースの複雑さを軽減できます。必要な行または列を2つだけ格納してください。

0 1 2 3 4 5
1 0 3 . . .
2 . . . . .
3 . . . . .
4 . . . . .
于 2012-07-03T07:20:36.793 に答える
2

ボトムアップ表現が必要な場合は、これで問題ありません。

MBoが示しているようにテーブルを埋めます

これは次のように実行できます。

for e from 0 to n:
  DP[0][e] = e
for b from 0 to n:
  DP[b][0] = b
for i from 1 to n:
   for j from 1 to n:
      DP[i][j] = DP[i-1][j-1] + DP[i-1][j] - DP[i][j-1]

これで、b、eに対するあなたの答えは単にDP[b][e]です。

于 2012-07-03T07:25:06.010 に答える
2

汎用の自動メモ化に関するこの最近のブログ投稿をご覧ください。作成者は、などのさまざまなデータ構造について説明します。警告：テンプレートを多用するコードを使用します。std::mapstd::unordered_map

于 2012-07-03T07:21:04.933 に答える
1

2次元配列を使用して、O（n ^ 2）で実装できます（bとeの値の最大数としてnを想定）。i、jの現在の各値は、i-1、jとi-1、j-1およびi、j-1の値に依存します。i = 0、j=0の場合を処理するようにしてください。

于 2012-07-03T07:21:16.853 に答える