algorithm - 動的計画法と行列の使用

Question

動的計画法が行列を使用して問題を解決する方法について、私はいつも混乱しています。行列は、前のサブ問題の結果を格納するために使用されるため、後でより大きな問題の計算に使用できることを大まかに理解しています。

しかし、行列の次元をどのように決定し、行列の各行/列が表す値をどのように知るのでしょうか? つまり、マトリックスを構築する一般的な手順のようなものはありますか?

たとえば、値 c1、c2、....cn のコインを使用して S の金額を変更することに関心がある場合、行列の次元はどのようにする必要があり、各列/行は何を表す必要がありますか?

方向性のあるガイダンスが役立ちます。ありがとうございました！

Answer 1

この章では、それを非常によく説明しています 。

Answer 2

DP ソリューションで使用される配列は、ほとんどの場合、問題の状態空間の次元に基づいています。つまり、各パラメーターの有効な値です。

例えば

fib[i+2] = fib[i+1] + fib[i]

と同じです

def fib(i):
    return fib(i-1)+fib(i-2]

再帰関数にメモ化を実装することで、これをより明確にすることができます

def fib(i): 
    if( memo[i] == null ) 
         memo[i] = fib(i-1)+fib(i-2)
    return memo[i]

再帰関数に K 個のパラメーターがある場合、K 次元の行列が必要になる可能性があります。