1

特定の合計を変更するすべての可能な方法を見つける次のアルゴリズムは、本当にメモ化を使用していますか?

func count( n, m )
  for i from 0 to n
    for j from 0 to m
      if i equals 0
        table[i,j] = 1          
      else if j equals 0
        table [i,j] = 0
      else if S_j greater than i
        table[ i, j ] = table[ i, j - 1 ]
      else 
        table[ i, j ] = table[ i - S_j, j ] + table[ i, j - 1 ]
return table[ n, m ]

関数 count が呼び出されるたびに、テーブルを最初から埋め始めます。テーブルが特定の値に対して既に初期化されている場合でも、次にカウントが呼び出されると、これらの値は使用されず、i = 0 および j = 0 から再び開始されます。

4

1 に答える 1

1

これはメモ化ではありません。これは、動的プログラミング コードの例です。

コードを分析するには、まずメモ化と動的プログラミングを区別する必要があります。

メモ化はトップダウンのアプローチですが、動的プログラミングはボトムアップのアプローチです。

数値nの階乗を求める問題を考えてみましょう。

あなたがnを見つけているなら！以下の事実を利用して、

n! = n * (n-1)! and 0!=1

これはトップダウン アプローチの例です。

n の値は、値が 0! になるまでメモリに保持されます。(n-1)まで！返されます。欠点は、多くのスタック メモリを浪費することです。利点は、既に解決されているサブ問題を再計算する必要がないことです。サブ問題の解決策はメモリに保存されます。

しかし、あなたの問題にはトップダウンのアプローチがないため、メモ化はありません。

テーブル内のすべてのエントリは、以前に計算されたサブ問題のソリューションから直接取得されます。そこでは、ボトムアップのアプローチが使用されます。したがって、動的プログラミングを使用するコードがあります。

于 2013-04-14T10:48:51.627 に答える