大家好，我就是那个在B站讲算法的「华南溜达虎」。
在选择一份工作的时候你会考虑哪些因素呢？今天看到一位应届毕业生拒绝了月薪19k的工作，他说这份工作杂七杂八算下来年薪差不多有30w，但是有30%的时间需要国际出差，由于不喜欢出差就拒绝了offer。
评论区不少同学觉得这是一份美差，既可以工作又可以出去看世界。也有很多有过出差经历的同学表示确实扛不住出差的舟车劳顿。每个人对出差的接受程度不太一样，很多时候还要顾及家人的感受，你怎样看待出差呢？
25届秋招已经开始了，我组织了一个秋招群，大家可以交流学习心得、面试经验，分享工作机会，有啥问题也可以在群里咨询。在群里我整理了一百多家已经启动秋招企业的文档，以及投递入口，每天都会更新，大家只要按照这个文档海投就可以了。
大家互帮互助相信一定可以拿下秋招！计算机相关专业的同学可以 点击底部的「阅读原文」 加群。
言归正传，今天我们来分享一道高频面试题「最长公共子序列」。
题目描述
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如， "ace"是"abcde"的子序列，但"aec"不是"abcde"的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
举个例子：
输入：text1 = "abcde", text2 = "ace"
输出：3
解释：最长公共子序列是 "ace" ，它的长度为 3 。知识回顾
动态规划是一种通过将原问题分解为子问题来求解复杂问题的算法思想。它通常用于求解最优化问题，例如最长公共子序列、背包问题等。动态规划的核心思想是将原问题分解为若干个子问题，通过求解子问题的最优解推导出原问题的最优解。可以通过两点来判断一个问题能不能通过动态规划来解，一是该问题是否存在递归结构，二是对应的子问题能否记忆化。动态规划可以通过带备忘录的自上而下的递归和自下而上的迭代来分别实现。由于递归需要用到栈来实现，一些语言对递归的深度是有限制的，所以自下而上的迭代是动态规划的最佳实现方式。
思路解析
首先定义dp[i][j]为text1的[0, i)区间和text2的[0, j)区间的最长公共子序列。[0, i)区间的长度为i，[0, j)区间的长度为j。
接下来我们来看两种情况下的子问题分解：
text1[i-1] == text2[j-1]，这个时候text1的[0, i)区间和text2的[0, j)区间上的最长公共子序列就变成了text1的[0, i-1)区间和text2的[0, j-1)区间上的最长公共子序列加1。即dp[i][j] = dp[i-1][j-1] + 1。
text1[i-1] != text2[j-1]，这个时候text1的[0, i)区间和text2的[0, j)区间上的最长公共子序列就变成了text1的[0, i-1)区间和text2的[0, j)区间上的最长公共子序列 以及text1的[0, i)区间和text2的[0, j-1)区间上的最长公共子序列 中比较长的一个。即dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
通过上面分析知dp[i][j]依赖子问题dp[i-1][j-1]，dp[i][j-1]，dp[i-1][j]的结果，同样的dp[i][j-1]依赖子问题dp[i-1][j-2]，dp[i][j-2]，dp[i-1][j-1]的结果，这里会涉及到重复子问题dp[i-1][j-1]。该问题存在递归结构，并且存在大量子问题可以记忆化保存，所以可以通过动态规划来实现。
本题是经典的二维动态规划问题，要找到解决动态规划问题的两个突破点：推导出状态转移公式和边界条件处理。
根据上面的分析状态转移公式为：
对于边界条件，很明显dp[i][0] = 0且dp[j][0] = 0。
text1 = "abcde"， text2 = "ace"的推导过程如下图：
最终dp[5][3] = 3，最长公共子序列的长度为3。
下面我们给出c++和python的两种代码实现。
C++代码
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int text1_len = text1.length();
int text2_len = text2.length();
//定义二维dp数组，并初始化，dp[i][0]=0 dp[0][j]=0
vector<vector<int>> dp(text1_len + 1, vector<int>(text2_len + 1, 0));
for (int i = 0; i < text1_len; ++i) {
for (int j = 0; j < text2_len; ++j) {
//text1[i] == text2[j]
if (text1[i] == text2[j]) {
//状态转移公式
dp[i+1][j+1] = dp[i][j] + 1;
//text1[i] != text2[j]
} else {
//状态转移公式
dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1]);
}
}
}
return dp[text1_len][text2_len];
}
};
python代码
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
text1_len = len(text1)
text2_len = len(text2)
# 初始化一个二维dp数组，全部初始化为0
dp = [[0] * (text2_len + 1) for _ in range(text1_len + 1)]
# 填充dp数组
for i in range(text1_len):
for j in range(text2_len):
if text1[i] == text2[j]:
# 如果当前字符相等，那么dp[i+1][j+1]等于dp[i][j] + 1
dp[i+1][j+1] = dp[i][j] + 1
else:
# 如果当前字符不相等，取dp[i+1][j]和dp[i][j+1]的较大值
dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
# 返回dp[text1_len][text2_len]，即最长公共子序列的长度
return dp[text1_len][text2_len]
复杂度分析
时间复杂度： O(mn) ，其中m为text1的长度，n为text2的长度。
空间复杂度： O(mn) ，其中m为text1的长度，n为text2的长度。
号外
经常使用leetcode会员的同学可以使用我的优惠通道啦！
https://leetcode.cn/premium/?promoChannel=ldtiger ，年度会员有效期比官网多俩月，季度会员有效期比官网多两个星期，还有专属福利，需要的读者朋友可以找我了解。
今天的分享就到这里，希望大家能有所收获！
