###### tags: `練習題`

# Dynamic Programming
## [1143. Longest Common Subsequence](https://leetcode.com/problems/longest-common-subsequence)(<font color="FFC011">Medium</font>)

限制 :
> `1 <= text1.length, text2.length <= 1000`
> `text1` and `text2` consist of only lowercase English characters.

### Solution
利用 Dynamic programming 計算最長子序列。
1. 利用前面的結果推後面的結果
2. 減少計算量

演算法:
1. 建立一個從 text1 --> text2 的表格，如下圖所示:

| LCS | "" | text2[0] | text2[1] | ... | ... | text2[0] |
| -------- | -------- | -------- | -------- | -------- | -------- | -------- |
| "" | | | | | |
| text1[0] |
| text1[1] |
|...|
|...|
| text1[text1.size()-1] |

2. 比較 text1[m] 和 text2[n] 是否相同
1. 如果相同 : 看看 看看 m 和 n 是不是邊界，不是邊界就拿 text1[m]、text2[n]的值 +1。
2. 反之: `max(i > 0 ? record[i-1][j] : 0, j > 0 ? record[i][j-1] : 0)`

#### 時間複雜度: $O(text1*text2)$

#### 空間複雜度: $O(text1*text2)$

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        vector<vector<short>> record(text1.size()+1, vector<short>(text2.size() + 1));
        for(int i = 0; i < record.size(); i++)            record[i][0] = 0;
        for(int i = 0; i < record[0].size(); i++)         record[0][i] = 0;

        for(int i = 0; i < text1.size(); i++)
        {
            for(int j = 0; j < text2.size(); j++)
            {
                if(text1[i] == text2[j])
                {
                    record[i][j] = (i && j ? record[i-1][j-1] : 0) + 1;
                }
                else
                {
                    record[i][j] = max(i > 0 ? record[i-1][j] : 0, j > 0 ? record[i][j-1] : 0);
                }
            }
        }
        return record[text1.size()-1][text2.size()-1];
    }
};

reference : [link](https://emmielin.medium.com/leetcode-%E7%AD%86%E8%A8%98-1143-longest-common-subsequence-b6c7eebd1328)