0

秋学期は動的計画法理論を勉強しましたが、ブラッシュアップしてさらに勉強を続けようと思っています。私は現在、この TopCoder 記事で述べられているように、LCS 問題への単純なアプローチを試みています:動的プログラミング

アルゴリズムは次のとおりです。

function LCS(S, T)
   if S is empty or T is empty then
      return empty string

   if first char of S == first char of T then
       return (first char of S) + LCS(S - first char, T - first char)

   otherwise // first chars are different
       return longer of LCS(S - first char, T) and LCS(S, T - first char)

たとえば、文字列「ABCDE」と「DACACBE」の場合、最も長い共通サブシーケンスは「ACE」です。

ただし、正しい「ACE」ではなく、有効な部分文字列「ABE」を出力します。実装の順序の何が問題になっていますか?

#include <iostream>
#include <string>
using namespace std;


string LCS(string s, string t);

int main(){
  string A = "ABCDE";
  string B = "DACACBE";
  cout << LCS(A,B) << endl;
  return 0;
}

string LCS(string s, string t){

  string sSub = "";
  string tSub = "";
  if(!s.empty())
    sSub = s.substr(1);
  if(!t.empty())
    tSub = t.substr(1);

  if(s.empty() || t.empty()){
    return ""; // return an empty string if either are empty
  }

  if(s[0] == t[0]){
    string firstOfS = "";
    firstOfS += s[0];
    firstOfS += LCS(sSub, tSub);
    return s[0] + LCS(sSub, tSub);
  }

  else{
    string a = LCS(sSub, t);
    string b = LCS(s, tSub);
    if(a.length() > b.length()){
      return a;
    }
    else{
      return b;
    }
  }
}
4

1 に答える 1

0

Phamが言ったように、どちらも正しいですが、なぜそれがコードの最後の部分が原因なのか疑問に思っている場合 

  else{
    if(a.length() > b.length()){
      return a;
    }
    else{
      return b;
    }
  }

a.length() = b.length() の場合、常に b を返します。長さが同じだからといって、それらが等しいというわけではありません。それがあなたが別の答えを持っている理由ですが、正しいものです:)

于 2015-12-23T03:34:14.980 に答える