❀ 題目傳送門 ❀

https://zerojudge.tw/ShowProblem?problemid=d231

❀ 解題小技巧 ❀

經典的 LCS(最長共同子序列) 題目，只要稍做一下變化就可AC。
想法是醬的：
我們要求的是兩串字中一樣的最大值，假設第一串字的每個字元的編號為 0 ~ x，第二串字的每個字元的編號為 0 ~ y。

  • 若兩字串最後一字相同
    要求的東西：0 ~ x-1 字與 0 ~ y-1 字相同最大值
  • 若兩字串最後一字不相同
    要求的東西：0 ~ x-1 字與 0 ~ y 字相同最大值、0 ~ x 字與 0 ~ y-1 字相同最大值，比較後較大者

附圖說明

❀ 參考程式碼 ❀

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
using namespace std;

int main(){
  string dp[55][55];
  for(int i = 0; i < 55; i++){
    for(int j = 0; j < 55; j++){
      dp[i][j] = "";
    }
  }
  string n, m;
  cin >> n >> m;
  for(int x = 1; x <= n.length(); x++){
    for(int y = 1; y <= m.length(); y++){
      if (n[x-1] == m[y-1]){
        dp[x][y] = dp[x-1][y-1]+n[x-1];
      }
      else{
        dp[x][y] = dp[x-1][y].length() > dp[x][y-1].length() ? dp[x-1][y] : dp[x][y-1];
      }
    }
  }
  if(dp[n.length()][m.length()] != "")
    cout << dp[n.length()][m.length()];
  else
    cout << "E";
  return 0;
}