0

長さkの増加するシーケンスの数をn個で見つける方法が難しいと感じています。私はそれがLIS問題を使用していることを知っており、どうにかしてそれを修正する必要がありますが、今はその方法を理解しています。複雑さはO(k*n^2)DPソリューションです。ヒントを教えて、少し説明してください。

4

1 に答える 1

1

少し遅れるかもしれませんが、これは役立つ場合があります。

この問題を解決するために使用される2つのアルゴリズム（私が知る限り）があります。O（n ^ 2 * k）の複雑さを持つものについて説明します。

このアルゴリズムはDPソリューションを使用します。それはLIS問題のひねりです。LIS問題では、1D配列を使用して、要素iまでのLISの長さを格納します。つまり、dp[i]=要素iまでのLISの長さです。これにより、次のようなアルゴリズムが作成されます。

/* let dp[] be the array that stores the length of the LIS found so far.
 v[] is the array of the values

 LIS(0) = 1
 LIS(i) = 1 + max(LIS(j) where j in [1..i-1] and v[j] < v[i]);
*/

dp[0] = 1;
for (int i=1 ; i<n ; i++)
    for (int j=0 ; j<i ; j++) if (v[j] < v[i])
        dp[i] = 1 + max(dp[i], dp[j]);

次に、これを別のレベルに引き上げて、長さkの増加するサブシーケンスの量を取得できます。アルゴリズムは同じ原理を使用します。

/*
  dp[i][k] -> Stores the number of subsequences of length k until character i
  v[] -> The values
  n -> The size of the array
  K -> the number of IS we are looking for

  The idea is to increment the value of this quantity, by the amount of the sequences
  found in the same character and the previous length. This will be better ilustrated int 
  the algorithm
*/

int totalIS = 0;
for (int i=0 ; i<n ; i++) {
    dp[i][1] = 1; // Number of subsequences of length 1 until element i
    for (int k=2 ; k<=K ; k++) { // For all the possible sizes of subsequence until k
        for (int j=0 ; j<i ; j++) if (v[j] < v[i]) {
            dp[i][k] += dp[j][k-1]; // Increment the actual amount by dp[j][k-1], which means
                                // the amound of IS of length k-1 until char j
        }
    }
    totalIS += dp[i][K]; // This can also be done in a separated cycle.
}

// The total amount of IS of length K is in totalIS

ご不明な点がございましたら、お気軽にお問い合わせください。

于 2013-05-06T16:12:25.040 に答える