题解 | #Coincidence#

/*
描述
Find a longest common subsequence of two strings.
输入描述：
First and second line of each input case contain two strings of lowercase character a…z. There are no spaces before, inside or after the strings. Lengths of strings do not exceed 100.
输出描述：
For each case, output k – the length of a longest common subsequence in one line.
*/

#include<iostream>
#include<string>
#include<vector>

using namespace std;

int main() {
    string strA;
    string strB;
    cin >> strA;
    cin >> strB;
    int n = strA.size(), m = strB.size();
    int** dp = new int* [n+1];
    for (int i = 0; i < n+1; ++i) {
        dp[i] = new int[m+1] {0};
    }
    for (int i = 1; i < n + 1; ++i) {
        for (int j = 1; j < m + 1; ++j) {
            if (strA[i - 1] == strB[j - 1]) {
            // 此时A,B串同时往后移动一位，此为贪心解法，不过此时贪心即为最优解 (optimal solution)
                dp[i][j] = dp[i - 1][j - 1] + 1;        
            }
            else {
            // 此时最大值为以下二者之一：1. A往后移动一位，B不动；2.B往后移动一位，A不动 （因为A[i-1], B[j]和 A[i], B[j-1]均可能匹配，而A[i],B[j]一定不匹配）
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);        
            }
        }
    }
    cout << dp[n][m]<<endl;

    for (int i = 0; i < n + 1; ++i) {
        delete [] dp[i];
    }
    delete [] dp;

    return 0;
}