- 121. 买卖股票的最佳时机
- 122. 买卖股票的最佳时机 II
- 123. 买卖股票的最佳时机 III
- 188. 买卖股票的最佳时机 IV
- 309. 最佳买卖股票时机含冷冻期
- 714. 买卖股票的最佳时机含手续费
- 300. 最长递增子序列
- 674. 最长连续递增序列
- 718. 最长重复子数组
- 1143. 最长公共子序列
- 总结
1 买卖股票的最佳时机
- 题目链接：121. 买卖股票的最佳时机
1.1 题目描述
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0。
示例1:
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例2:输入: prices = [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
1.2 思路
本题只能买卖一次股票，用贪心算法的话相当于当天卖出并买入，实际上就是买卖一次。用动态规划的话，首先定义一个DP数组，其含义为当天的最大利益/最小支出，其中dp[i][0]指手里没有股票，由前一天没有股票和前一天有股票当天卖出两种情况转移而来， 而dp[i][1]则是当天手里有股票，由前一天手里有股票或者当天买入股票两种情况转移而来。因此易得状态转移方程为:
注意，dp[i][1]的更新，实际上就是比较股票的交割，找个低价的买，切记不能写成
max(dp[i-1][1], dp[i-1][0]- prices[i]),这样写变成了多次买卖股票了。
完整代码如下：
Cpp实现
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
int dp[n][2];
dp[0][0] = 0, dp[0][1] = -prices[0];
for(int i = 1; i < n; ++i){
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);
dp[i][1] = max(dp[i-1][1], - prices[i]);
}
return dp[n-1][0];
}
};C实现
int maxProfit(int* prices, int pricesSize){
int dp[pricesSize+1][2];
dp[0][0] = 0, dp[0][1] = -prices[0]; //0表示当天手里没股票，1表示当天手里有股票
for(int i = 1; i <= pricesSize; i++){
dp[i][0] = fmax(dp[i-1][1] + prices[i-1], dp[i-1][0]);
//dp[i][1] = fmax(dp[i-1][0] - prices[i-1], dp[i-1][1]);
dp[i][1] = fmax(- prices[i-1], dp[i-1][1]); //只允许一次操作
}
return dp[pricesSize][0];
} 2 买卖股票的最佳时机 II
- 题目链接：122. 买卖股票的最佳时机 II
2.1 题目描述
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大 利润 。
示例1:
输入: prices = [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
总利润为 4 + 3 = 7 。
示例2:
输入: prices = [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
总利润为 4 。
示例3:
输入: prices = [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。
2.2 思路
这一题其实就是允许多次买卖，实质上和上一题是一样的。
完整代码如下：
Cpp实现
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
int dp[n][2];
dp[0][0] = 0, dp[0][1] = -prices[0];
for(int i = 1; i < n; ++i){
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);
dp[i][1] = max(dp[i-1][1], dp[i-1][0]- prices[i]);
}
return dp[n-1][0];
}
};C实现
int maxProfit(int* prices, int pricesSize){
/*int ans = 0;
for(int i = 1; i < pricesSize; i++){
int diff = prices[i]- prices[i-1];
if(diff> 0){
ans += diff;
}
}
return ans;*/
int dp[pricesSize][2];
dp[0][0] = 0, dp[0][1] = -prices[0];
for(int i = 1; i < pricesSize; i++){
dp[i][0] = fmax(dp[i-1][0], dp[i-1][1] + prices[i]);
dp[i][1] = fmax(dp[i-1][0] - prices[i], dp[i-1][1]);
}
return fmax(dp[pricesSize-1][0], dp[pricesSize-1][1]);
} 3 买卖股票的最佳时机 III
- 题目链接：123. 买卖股票的最佳时机 III
3.1 题目描述
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例1:
输入: prices = [3,3,5,0,0,3,1,4]
输出: 6
解释: 在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。
示例2:
输入: prices = [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例3:
输入: prices = [7,6,4,3,1]
输出: 0
解释: 在这个情况下, 没有交易完成, 所以最大利润为 0。
示例4:
输入: prices = [1]
输出: 0
3.2 思路
这一次有买卖次数至多为2的限制，因此创建dp数组dp[2][2],第一行依次代表买入1次、卖出1次；第二行则是买入2次、卖出2次。买入1次为没买过当天买入和之前已经买入1次没卖出两种情况种的大者，即dp[0][0] = max(dp[0][0], -prices[i])，其实就是比较价格，选择价格低的一天买入；卖出1次则由买入1次转移而来，因而有dp[0][1] = max(dp[0][1], dp[0][0] + prices[i])；买入2次需要在买入1次卖出1次的前提下转移：dp[1][0] = max(dp[1][0], dp[0][1] - prices[i]); 类似的，卖出两次需要在买入2次的前提下转移而来：dp[1][1] = max(dp[1][1], dp[1][0] + prices[i]).
完整代码如下：
Cpp实现
class Solution {
public:
int maxProfit(vector<int>& prices) {
/*
int dp[2][2] = {0}；
dp[0][0] = -prices[0], dp[1][0] = -prices[0];
for(int i = 1; i < prices.size(); ++i){
dp[0][0] = max(dp[0][0], -prices[i]);
dp[0][1] = max(dp[0][1], dp[0][0] + prices[i]);
dp[1][0] = max(dp[1][0], dp[0][1] - prices[i]);
dp[1][1] = max(dp[1][1], dp[1][0] + prices[i]);
}
return dp[1][1];
*/
int buy1 = -prices[0], buy2 = -prices[0], sell1 = 0, sell2 = 0;
for(int i = 1; i < prices.size(); ++i){
buy1 = max(buy1, -prices[i]);
sell1 = max(sell1, buy1 + prices[i]);
buy2 = max(buy2, sell1 - prices[i]);
sell2 = max(sell2, buy2 + prices[i]);
}
return sell2;
}
};C实现
int maxProfit(int* prices, int pricesSize){
/*int ans = 0;
for(int i = 1; i < pricesSize; i++){
int diff = prices[i]- prices[i-1];
if(diff> 0){
ans += diff;
}
}
return ans;*/
int dp[pricesSize][2];
dp[0][0] = 0, dp[0][1] = -prices[0];
for(int i = 1; i < pricesSize; i++){
dp[i][0] = fmax(dp[i-1][0], dp[i-1][1] + prices[i]);
dp[i][1] = fmax(dp[i-1][0] - prices[i], dp[i-1][1]);
}
return fmax(dp[pricesSize-1][0], dp[pricesSize-1][1]);
} 4 买卖股票的最佳时机 IV
- 题目链接：188. 买卖股票的最佳时机 IV
4.1 题目描述
给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例1:
输入: k = 2, prices = [2,4,1]
输出: 2
解释: 在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
示例2:
输入: k = 2, prices = [3,2,6,5,0,3]
输出: 7
解释: 在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。
4.2 思路
其实就是上一题的次数改变，套路一样。
完整代码如下：
Cpp实现
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
if(prices.size() == 0) return 0;
int dp[k+1][k+1];
memset(dp, 0, sizeof(dp));
for(int i = 1; i <= k; ++i){
dp[i][i-1] = -prices[0];
}
for(int i = 1; i < prices.size(); ++i){
for(int j = 1; j <= k; ++j){
dp[j][j-1] = max(dp[j][j-1], dp[j-1][j-1] - prices[i]);
dp[j][j] = max(dp[j][j], dp[j][j-1] + prices[i]);
}
}
return dp[k][k];
}
};C实现
int maxProfit(int* prices, int pricesSize){
/*int ans = 0;
for(int i = 1; i < pricesSize; i++){
int diff = prices[i]- prices[i-1];
if(diff> 0){
ans += diff;
}
}
return ans;*/
int dp[pricesSize][2];
dp[0][0] = 0, dp[0][1] = -prices[0];
for(int i = 1; i < pricesSize; i++){
dp[i][0] = fmax(dp[i-1][0], dp[i-1][1] + prices[i]);
dp[i][1] = fmax(dp[i-1][0] - prices[i], dp[i-1][1]);
}
return fmax(dp[pricesSize-1][0], dp[pricesSize-1][1]);
} 5 最佳买卖股票时机含冷冻期
- 题目链接：309. 最佳买卖股票时机含冷冻期
5.1 题目描述
给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例1:
输入: prices = [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
示例2:
输入: prices = [1]
输出: 0
5.2 思路
股票问题一般有两个状态：当天结束后手里有股票和手里没股票。这一题多了一个状态，即当天结束后是否为冷却期，因而定义dp数组时，其第二维应该设为3，即dp[n][3]:
dp[i][0]代表第i天手里没有股票且不处于冷却期时的收益，由前一天没有股票和前一天处于冷却期两种情况转移而来。dp[i][1]代表第i天手里有股票时的收益，由前一天有股票和前一天为没有股票且非冷却期转移而来。dp[i][2]代表第i天手里没有股票且处于冷却期时的收益，由前一天有股票且卖出转移而来。
状态转移方程为：
注意， dp数组的含义是第i天结束后的价值，可以理解为当天进行操作后第二天的状态。这也就是dp[i][0]为什么是从前一天没有股票和前一天处于冷却期两种情况转移而来，前一种情况很好理解，就是前一天不买股票，所以前一天之后的状态就是0,而当天之后为0就是在当天状态为0的情况下不买股票转移而来；第二种情况则是前一天操作过后为冷却期，也就是当天是冷却期，那肯定不能买入股票，因而当天过后的状态就是0.
完整代码如下：
Cpp实现
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
//未经优化
int dp[n][3]; //0表示当天过后无股票，1表示有股票，2表示当天过后为冷却期
/*dp[0][0] = 0;
dp[0][1] = -prices[0];
dp[0][2] = 0;
bool flag = false;
for(int i = 1; i < n; ++i){
dp[i][0] = max(dp[i-1][2], dp[i-1][0]); //无股票且非冷却期
dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i]); //有股票
dp[i][2] = dp[i-1][1] + prices[i]; //无股票且处于冷却期
}
return max(dp[n-1][0], dp[n-1][2]);*/
//空间优化后
int dp0 = 0, dp1 = -prices[0], dp2 = 0;
for(int i = 1; i < n; ++i){
int next_dp0 = max(dp0, dp2);
int next_dp1 = max(dp0 - prices[i], dp1);
dp2 = dp1 + prices[i];
dp0 = next_dp0, dp1 = next_dp1;
}
return max(dp0, dp2);
}
};C实现
int maxProfit(int* prices, int pricesSize){
//未优化
/*int dp[pricesSize][3];
dp[0][0] = 0, dp[0][1] = -prices[0], dp[0][2] = 0;
for(int i = 1; i<pricesSize; i++){
dp[i][0] = fmax(dp[i-1][0], dp[i-1][2]); //没股票,不冷冻
dp[i][1] = fmax(dp[i-1][1], dp[i-1][0]-prices[i]); //有股票
dp[i][2] = dp[i-1][1]+prices[i]; //没股票，冷冻
}
return fmax(dp[pricesSize-1][0], dp[pricesSize-1][2]);*/
//优化后
int dp[3];
dp[0] = 0, dp[1] = -prices[0], dp[2] = 0;
for(int i = 1; i<pricesSize; i++){
int dp0 = fmax(dp[0], dp[2]); //没股票,不冷冻
int dp1 = fmax(dp[1], dp[0]-prices[i]); //有股票
int dp2 = dp[1]+prices[i]; //没股票，冷冻
dp[0] = dp0, dp[1] = dp1, dp[2] = dp2;
}
return fmax(dp[0], dp[2]);
} 6 买卖股票的最佳时机含手续费
- 题目链接：714. 买卖股票的最佳时机含手续费
6.1 题目描述
给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
示例1:
输入: prices = [1, 3, 2, 8, 4, 9], fee = 2
输出: 8
解释: 能够达到的最大利润:
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8
示例2:
输入: prices = [1,3,7,5,10,3], fee = 3
输出: 6
示例3:
输入:
输出:
6.2 思路
/analysis_of_question_and_solving_thought_here/
完整代码如下：
Cpp实现
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
int n = prices.size();
int dp[n][2];
dp[0][0] = 0, dp[0][1] = -prices[0];
for(int i = 1; i < n; ++i){
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i] - fee);
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]);
}
return dp[n-1][0];
/*
int dp[2] = {0, -prices[0]};
for(int i = 1; i < n; ++i){
int new_dp0 = max(dp[0], dp[1] + prices[i] - fee);
int new_dp1 = max(dp[1], dp[0] - prices[i]);
dp[0] = new_dp0, dp[1] = new_dp1;
}
return dp[0];
*/
}
};C实现
int maxProfit(int* prices, int pricesSize, int fee){
/*int dp[pricesSize][2];
dp[0][0] = 0, dp[0][1] = -prices[0];
for(int i = 1; i < pricesSize; i++){
dp[i][0] = fmax(dp[i-1][1]+prices[i]-fee, dp[i-1][0]);
dp[i][1] = fmax(dp[i-1][1], dp[i-1][0]-prices[i]);
}
return dp[pricesSize-1][0];*/
int dp[2] = {0, -prices[0]};
for(int i = 1; i < pricesSize; i++){
int newdp0 = fmax(dp[1]+prices[i]-fee, dp[0]);
int newdp1 = fmax(dp[1], dp[0]-prices[i]);
dp[0] = newdp0;
dp[1] = newdp1;
}
return dp[0];
} 7 最长递增子序列
- 题目链接：300. 最长递增子序列
7.1 题目描述
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例1:
输入: nums = [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例2:
输入: nums = [0,1,0,3,2,3]
输出: 4
示例3:
输入: nums = [7,7,7,7,7,7,7]
输出: 1
7.2 思路
定义一个dp数组，其含义为包括当前遍历到的数字在内的最长递增子序列长度，因而需要用一个ans变量来记录整个数组中所出现的最长递增子序列长度(不一定是在最后一位出现，因此遍历过程中需要更新答案ans，而不是最后直接返回dp[n-1])。
完整代码如下：
Cpp实现
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
int dp[n];
for(int i = 0; i < n; ++i){
dp[i] = 1;
}
int ans = 1;
for(int i = 1; i < n; ++i){
for(int j = 0; j < i; ++j){
if(nums[j] < nums[i]){
dp[i] = max(dp[i], dp[j] + 1);
}
}
ans = max(ans, dp[i]);
}
return ans;
}
};C实现
int lengthOfLIS(int* nums, int numsSize){
int dp[numsSize], ans = 1;
memset(dp, 0, sizeof(dp));
for(int i = 0; i < numsSize; i++){
dp[i] = 1;
for(int j = 0; j < i; j++){
if(nums[i] > nums[j]){
dp[i] = fmax(dp[i], dp[j]+1);
}
ans = fmax(ans, dp[i]);
}
}
return ans;
} 8 最长连续递增序列
- 题目链接：674. 最长连续递增序列
8.1 题目描述
给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。
连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。
示例1:
输入: nums = [1,3,5,4,7]
输出: 3
解释: 最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。
示例2:
输入: nums = [2,2,2,2,2]
输出: 1
解释: 最长连续递增序列是 [2], 长度为1。
8.2 思路
相比DP, 用滑动窗口更为简单。
完整代码如下：
Cpp实现
class Solution {
public:
int findLengthOfLCIS(vector<int>& nums) {
int dp[nums.size()], result = 1;
for(int i = 0; i < nums.size(); ++i){
dp[i] = 1;
}
for(int i = 1; i < nums.size(); ++i){
if(nums[i] > nums[i-1]){
dp[i] = dp[i-1] + 1;
}
result = max(result, dp[i]);
}
return result;
}
};C实现
int findLengthOfLCIS(int* nums, int numsSize){
int ans = 1, curlen = 1;
for(int i = 1; i < numsSize; i++){
if(nums[i] > nums[i-1]){
curlen++;
//if(i == 8) return curlen;
}else{
ans = fmax(ans, curlen);
curlen = 1;
}
}
return fmax(ans, curlen);
} 9 最长重复子数组
- 题目链接：718. 最长重复子数组
9.1 题目描述
给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。
示例1:
输入: nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出: 3
解释: 长度最长的公共子数组是 [3,2,1] 。
示例2:
输入: nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
输出: 5
9.2 思路
dp[i][j]的含义：nums1中前i个数字和nums2中前j个数字中重叠的长度。
完整代码如下：
Cpp实现
class Solution {
public:
int findLength(vector<int>& nums1, vector<int>& nums2) {
int n1 = nums1.size(), n2 = nums2.size();
int ans = 0;
//二维dp数组
/*
int dp[n1+1][n2+1];
memset(dp, 0, sizeof(dp));
for(int i = 1; i <= n1; ++i){
for(int j = 1; j <= n2; ++j){
if(nums1[i-1] == nums2[j-1]){
dp[i][j] = dp[i-1][j-1] + 1;
ans = max(ans, dp[i][j]);
if(ans == n1 || ans == n2) return ans;
}
}
}*/
//滚动数组
int dp[n2+1];
memset(dp, 0, sizeof(dp));
for(int i = 1; i <= n1; ++i){
for(int j = 1; j <= n2; ++j){
if(nums1[i-1] == nums2[j-1]){
dp[j] = dp[j-1] + 1;
ans = max(ans, dp[j]);
if(ans == n1 || ans == n2) return ans;
}
}
}
return ans;
}
};C实现
int findLength(int* nums1, int nums1Size, int* nums2, int nums2Size){
int n1 = nums1Size, n2 = nums2Size;
int dp[n1+1][n2+1];
memset(dp, 0, sizeof(dp));
int ans = 0;
for(int i = 1; i <= n1; ++i){
for(int j = 1; j <= n2; ++j){
if(nums1[i-1] == nums2[j-1]){
dp[i][j] = dp[i-1][j-1] + 1;
ans = fmax(ans, dp[i][j]);
if(ans == n1 || ans == n2) return ans;
}
}
}
return ans;
} 10 最长公共子序列
- 题目链接：1143. 最长公共子序列
10.1 题目描述
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
- 例如，
"ace"是"abcde"的子序列，但"aec"不是"abcde"的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
示例1:
输入: text1 = “abcde”, text2 = “ace”
输出: 3
解释: 最长公共子序列是 “ace” ，它的长度为 3 。
示例2:
输入: text1 = “abc”, text2 = “abc”
输出: 3
解释: 最长公共子序列是 “abc” ，它的长度为 3 。
示例3:
输入: text1 = “abc”, text2 = “def”
输出: 0
解释: 两个字符串没有公共子序列，返回 0 。
10.2 思路
dp[i][j]的含义为text1[0...i]和text2[0...j]的最长公共子序列长度。
完整代码如下：
Cpp实现
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int m = text1.length(), n = text2.length();
int dp[m+1][n+1];
memset(dp, 0, sizeof(dp));
int ans = 0;
for(int r = 1; r <= m; ++r){
for(int c = 1; c <= n; ++c){
if(text1[r-1] == text2[c-1]){
dp[r][c] = dp[r-1][c-1] + 1;
}else{
dp[r][c] = max(dp[r-1][c], dp[r][c-1]);
}
ans = max(ans, dp[r][c]);
}
}
return ans;
}
};C实现
int longestCommonSubsequence(char * text1, char * text2){
int dp[strlen(text1)+1][strlen(text2)+1];
memset(dp, 0, sizeof(dp));
dp[0][0] = 0;
for(int i = 1; i <= strlen(text1); i++){
for(int j = 1; j <= strlen(text2); j++){
if(text1[i-1] == text2[j-1]){
dp[i][j] = dp[i-1][j-1] + 1;
}else{
dp[i][j] = fmax(dp[i-1][j], dp[i][j-1]);
}
}
}
return dp[strlen(text1)][strlen(text2)];
}
