动态规划

简介

动态规划最核心两步：

状态表示：dp[i]代表什么
状态转移方程：如何利用已有的dp求解dp[i]

只要这两步搞对了，就完成了动态规划的%95

剩下的就是细节问题：

dp初始化顺序（有时是倒序）
处理边界问题（n过小则直接返回，避免越界）

这是动态规划第一小节，简单介绍下dp主要类型

斐波那契数列模型
路径问题
简单多状态 dp 问题
子数组系列
子序列问题
回文串问题
两个数组的 dp 问题
01 背包问题
完全背包问题
二维费用的背包问题
似包非包
卡特兰数

一.斐波那契数列模型

1.第N个泰伯纳妾数

link:1137. 第 N 个泰波那契数 - 力扣（LeetCode）

code

class Solution {
public:int tribonacci(int n) {if(n == 0) return n;if(n == 1 || n == 2) return 1;// 动态规划vector<int> dp(n + 1, -1);// initdp[0] = 0; dp[1] = dp[2] = 1;for(int i = 3; i < dp.size();i++){dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];}return dp[n];}
};

2.三步问题

link:面试题 08.01. 三步问题 - 力扣（LeetCode）

code

class Solution {
public:const int MOD = 1e9 + 7;int waysToStep(int n) {// 状态表示：dp[n] 表示上n节台阶的方式数// 状态转移：dp[n] = dp[n - 1] + dp[n - 2] + dp[n - 3];vector<int> dp(n + 5 , -1);// init dpdp[1] = 1; dp[2] = 2; dp[3] = 4;if(n <= 3) return dp[n];for(int i = 4; i < dp.size(); i++){dp[i] = ((dp[i - 1] + dp[i - 2])%MOD + dp[i - 3])%MOD;}return dp[n];}
};

3.使用最小花费爬楼梯

link:746. 使用最小花费爬楼梯 - 力扣（LeetCode）

code

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {// 状态表示:dp[i]表示爬到第i台阶需要的最小费用/不包括i台阶// 状态转移:dp[i] = min(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1])vector<int> dp(cost.size() + 1, -1);// init dpdp[0] = dp[1] = 0;// dpfor(int i = 2; i < dp.size(); i++){dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);}return dp[cost.size()];}
};

4.解码方法

link:91. 解码方法 - 力扣（LeetCode）

code

class Solution {
public:int numDecodings(string s) {// 状态表示：dp[i]表示s[0,i](包含s[i])解码方法总数// 状态转移: dp[i] = valid(s[i])?dp[i - 1]:0 + valid(s[i-1,i]?dp[i - 2]:0if(s.size() == 1){return valid(string(1, s[0])) ? 1 : 0;}if(s.size() == 2){return (valid(string(1, s[0])) && valid(string(1, s[1]))) + valid(s.substr(0, 2));}vector<int> dp(s.size(), 0);// init dpdp[0] = valid(string(string(1, s[0]))) ? 1 : 0;dp[1] = (valid(string(1, s[0])) && valid(string(1, s[1]))) + valid(s.substr(0, 2));// dpfor(int i = 2; i < dp.size(); i++){dp[i] = (valid(string(1, s[i])) ? dp[i - 1] : 0) + (valid(s.substr(i-1, 2))?dp[i - 2] : 0);}return dp[s.size() - 1];}bool valid(string s){if(s.size() == 1) return s[0] >= '1' && s[0] <= '9';else// s.size()==2{return stoi(s) >= 10 && stoi(s) <= 26;}}
};

二.路径问题

5.不同路径

link:62. 不同路径 - 力扣（LeetCode）

tips:

此问题中，我们可以多开一行和一列，从1下标开始初始有效值，

这样可以避免状态转移时的下标越界问题

code

class Solution {
public:vector<vector<int>> dp;int uniquePaths(int m, int n) {// dp[i][j]:从(0, 0)到(i, j)// dp[i][j] = dp[i-1][j] + dp[i][j-1]dp = vector<vector<int>>(m + 5, vector<int>(n + 5, 0));// dp此时可以不用-1标记是否初始化， 因为是按顺序初始化的// init dpdp[0][1] = 1;// 间接初始化dp[1][1]， 防止for循环覆盖dp[1][1];// dpfor(int i = 1; i <= m; i++)for(int j = 1; j <= n; j++){dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}return dp[m][n];}
};

6.不同路径II

link:63. 不同路径 II - 力扣（LeetCode）

code

class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& grid) {// dp[i][j]:起点到(i, j)的路径数// dp[i][j] = grid[i][j] == 1 ? 0 : dp[i-1][j] + dp[i][j-1];// 注意dp多开一行和一列， 从下标1开始初始化vector<vector<int>> dp(grid.size() + 1, vector<int>(grid[0].size() + 1, 0));// init dpdp[0][1] = 1;// 间接初始化dp[1][1]// dpfor(int i = 1; i <= grid.size(); i++){for(int j = 1; j <= grid[0].size(); j++){dp[i][j] = (grid[i-1][j-1] == 1 ? 0 : dp[i-1][j] + dp[i][j-1]);}}return dp[grid.size()][grid[0].size()];}
};

7.珠宝的最高价值

link:LCR 166. 珠宝的最高价值 - 力扣（LeetCode）

code

class Solution {
public:int jewelleryValue(vector<vector<int>>& frame) {// dp[i][j]:走到(i, j)能拿到的最大珠宝// dp[i][j] = max(dp[i-1][j], dp[i][j-1])+frame[i][j];// 多开一行一列， 从下标1初始化vector<vector<int>> dp(frame.size() + 1, vector<int>(frame[0].size() + 1, 0));for(int i = 1; i < dp.size(); i++){for(int j = 1; j < dp[0].size(); j++){dp[i][j] = max(dp[i-1][j], dp[i][j-1])+frame[i-1][j-1];//注意dp和frame下标不一致}}return dp[frame.size()][frame[0].size()];}
};

8.下降路径最小和

link:931. 下降路径最小和 - 力扣（LeetCode）

code

class Solution {
public:int minFallingPathSum(vector<vector<int>>& matrix) {// dp[i][j]:下降到(i, j)的下降路径最小和// dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]) + matrix[i][j]// 多开两行两列， 从下标1开始初始化// 相当于上下左右都围上了一圈， 避免越界vector<vector<int>> dp(matrix.size()+2, vector<int>(matrix[0].size()+2, INT_MAX));// init dpfor(int i = 1; i <= matrix.size(); i++){for(int j = 1; j <= matrix[0].size(); j++){if(i==1)dp[i][j] = matrix[i-1][j-1];else{dp[i][j] = matrix[i-1][j-1] + min(min(dp[i-1][j-1], dp[i-1][j]), dp[i-1][j+1]);}}}int ans = INT_MAX;for(int col = 1; col <= matrix[0].size(); col++){ans = min(ans, dp[matrix.size()][col]);}return ans;}
};

9.最小路径和

link:64. 最小路径和 - 力扣（LeetCode）

code

class Solution {
public:int minPathSum(vector<vector<int>>& grid) {// dp[i][j]:从左上角到(i,j)的数字总和最小值// dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])// dp多开一行一列， 从下标1开始初始化。防止下标越界vector<vector<int>> dp(grid.size()+1, vector<int>(grid[0].size()+1, INT_MAX));// init dpdp[0][1] = 0;// 间接初始化dp[1][1]// dpfor(int i = 1; i <= grid.size(); i++){for(int j = 1; j <= grid[0].size(); j++){dp[i][j] = grid[i-1][j-1] + min(dp[i-1][j], dp[i][j-1]);}}return dp[grid.size()][grid[0].size()];}
};

10.地下城游戏

link:174. 地下城游戏 - 力扣（LeetCode）

code1 & code2的dp状态表示稍有不同，但是思路相同

code1

class Solution {
public:int calculateMinimumHP(vector<vector<int>>& g) {// 过程最小值：min(S1~Sn), 代表的是骑士在这条路上血量最低值（假设骑士初始血量0）, 也就是所求所需最低初始的健康点数-1的相反数// dp[i][j] : 从（i, j)开始到终点的过程最小值// 不给dp开多余空间, dp时注意处理初始化与边界情况即可// 注意dp时反向dpvector<vector<int>> dp(g.size(), vector<int>(g[0].size(), 0));// init dp// dpfor(int i = g.size()-1; i >= 0; i--){for(int j = g[0].size()-1; j >= 0; j--){if(i==g.size()-1 && j==g[0].size()-1) // for内初始化{dp[i][j] = g[i][j];continue;}int val1 = i+1 < g.size() ? min(g[i][j], g[i][j] + dp[i+1][j]) : INT_MIN;// 处理边界情况int val2 = (j+1 < g[0].size())?min(g[i][j], g[i][j] + dp[i][j+1]):INT_MIN;dp[i][j] = max(val1, val2);}printf("\n");}return dp[0][0] >= 1 ? 1 : -dp[0][0] + 1;}
};

code2

class Solution {
public:int calculateMinimumHP(vector<vector<int>>& d) {// dp[i][j]：从（i, j)出发到终点所需最低初始健康点数// dp[i][j] = min(dp[i][j+1], dp[i+1][j]) - d[i][j]// dp[i][j] = max(1, dp[i][j])// dp时init dp即可// 注意dp顺序， 倒序dpint m = d.size(), n = d[0].size();vector<vector<int>> dp(m+1, vector<int>(n+1, INT_MAX));// init dpdp[m-1][n] = dp[m][n-1] =  1;// dpfor(int i = m-1; i >= 0; i--){for(int j = n - 1; j >= 0; j--){dp[i][j] = min(dp[i+1][j], dp[i][j+1]) - d[i][j];dp[i][j] = max(1, dp[i][j]);}}return dp[0][0];}
};

三.简单多状态dp问题

dp时如何判断使用哪几种状态？

多状态dp中，我们选择的dp状态们必须能覆盖所有情况，这样，状态推导时可以保证条件充足，状态转移会很轻松

具体示例建议参考6.买卖股票的最佳时机

决策描述/状态描述？

决策描述是指用发生了什么决策/事件（买入/卖出）来标记/描述dp[i]

状态描述是指使用该位置可能所处的状态来描述dp[i]

某个位置的状态描述，不仅可以用此位置的决策/发生事件（如买入/卖出）来标记状态，还可以使用状态（如持有/不持有）来标记状态。

特别是当不是每个位置都可能发生决策/事件时，我们应采用状态来标记位置，这样能保证覆盖所有情况，而如果采用决策标记方法，则会遗漏不做决策的可能

1.按摩师

link：面试题 17.16. 按摩师 - 力扣（LeetCode）

code1_单一状态dp

class Solution {
public:int massage(vector<int>& nums) {// dp[i]：从num[i]开始(包含nums[i])， 最优预约时长// dp[i] = nums[i] + max(dp[i+2], dp[i+3])  //不可能dp[i+4]因为此时可以选dp[i+2]if(nums.size() < 3){if(nums.size()==0)return 0;if(nums.size()==1)return nums[0];if(nums.size()==2)return max(nums[0], nums[1]);}vector<int> dp(nums.size(), 0);// init dpint sz = nums.size();dp[sz-1] = nums[sz-1];dp[sz-2] = nums[sz-2];dp[sz-3] = nums[sz-1] + nums[sz-3];// dpfor(int i = sz - 4; i >= 0; i--){dp[i] = nums[i] + max(dp[i + 2], dp[i + 3]);}return max(dp[0], dp[1]);}
};

code2-多状态dp

class Solution {
public:int massage(vector<int>& nums) {// 多状态dp// f[i]:选择nums[i]// g[i]:不选择nums[i]// f[i] = g[i-1] + nums[i]// g[i] = max(f[i-1], g[i-1])if(nums.size()==0)return 0;if(nums.size()==1) return nums[0];vector<int> f(nums.size(), 0);vector<int> g(nums.size(), 0);// init dpf[0] = nums[0]; g[0] = 0;// dpfor(int i = 1; i < nums.size(); i++){f[i] = g[i-1] + nums[i];g[i] = max(g[i-1], f[i-1]);}return max(g[nums.size()-1], f[nums.size()-1]);}
};

2.打家劫舍

link:198. 打家劫舍 - 力扣（LeetCode）

题意和上道题”按摩师“一样，此题主要为了给打家劫舍II做铺垫

code

class Solution {
public:int rob(vector<int> nums){// 不可连续， 每房子有偷和不偷两种状态// yes[i]： 偷nums[i]// no[i]:不偷nus[i]// yes[i] = no[i-1] + nums[i]// no[i] = max(no[i-1], yes[i-1])if(nums.size()==0)return 0;int sz = nums.size();vector<int> yes(sz);vector<int> no(sz);// init dpyes[0] = nums[0];no[0] = 0;// dpfor(int i = 1; i < sz; i++){yes[i] = no[i-1] + nums[i];no[i] = max(no[i-1], yes[i-1]);}return max(yes[sz-1], no[sz-1]);}
};

3.打家劫舍II

link：213. 打家劫舍 II - 力扣（LeetCode）

code

class Solution {
public:int rob(vector<int>& nums) {// 通过分情况讨论是否偷第一家， 消除环形影响，将问题转化为rob1的线性结构int yes = nums.size() > 3 ? nums[0] + rob1({nums.begin() + 2, nums.end()-1}) : nums[0];// 偷第一家 // 就不能偷最后一家int no = rob1({nums.begin() + 1, nums.end()});// 不偷第一家printf("yes:%d, no:%d\n", yes, no);return max(yes, no);}int rob1(vector<int> nums){// 不可连续， 每房子有偷和不偷两种状态// yes[i]： 偷nums[i]// no[i]:不偷nus[i]// yes[i] = no[i-1] + nums[i]// no[i] = max(no[i-1], yes[i-1])if(nums.size()==0)return 0;int sz = nums.size();vector<int> yes(sz);vector<int> no(sz);// init dpyes[0] = nums[0];no[0] = 0;// dpfor(int i = 1; i < sz; i++){yes[i] = no[i-1] + nums[i];no[i] = max(no[i-1], yes[i-1]);}return max(yes[sz-1], no[sz-1]);}
};

4.删除并获得点数

link:740. 删除并获得点数 - 力扣（LeetCode）

code1_多状态dp模拟

class Solution {
public:int deleteAndEarn(vector<int>& nums) {// 先将nums升序排序， 去重// 每个点两种状态：删除， 不删除// del[i]:删除num[i]情况下， 最大点数// sav[i]:不删除num[i]情况下， 最大点数// del[i] = (nums[i]-nums[i-1]>1)?max(sav[i-1], del[i-1]):sav[i-1]// sav[i] = nums[i] + ((nums[i]-nums[i-1]>1)?max(sav[i-1], del[i-1]):sav[i-1])// 预处理numsunordered_map<int, int> cnt;for(auto it = nums.begin(); it != nums.end(); it++){cnt[*it]++;}sort(nums.begin(), nums.end());auto it = unique(nums.begin(), nums.end());// 也可以set去重nums.erase(it, nums.end());int sz = nums.size();if(sz == 0)return 0;// check numsfor(int i = 0; i < sz; i++){printf("%d ", nums[i]);}printf("\n");// init dpvector<int> del(sz);vector<int> sav(sz);del[0] = nums[0]*cnt[nums[0]];sav[0] = 0;for(int i = 1; i < sz; i++){del[i] = nums[i]*cnt[nums[i]] + ((nums[i]-nums[i-1]>1)?max(sav[i-1], del[i-1]):sav[i-1]);sav[i] = max(sav[i-1], del[i-1]);}return max(del[sz-1], sav[sz-1]);}
};

code2-转化为打家劫舍

class Solution {
public:int deleteAndEarn(vector<int>& nums) {// 转化为打家劫舍I#define N (1e4 + 10)vector<int> arr(N, 0);// 预处理arrfor(auto e:nums)arr[e] += e;// 相同数消去时可以累加， 所以+=return rob1(arr);}int rob1(vector<int> nums){// 不可连续， 每房子有偷和不偷两种状态// yes[i]： 偷nums[i]// no[i]:不偷nus[i]// yes[i] = no[i-1] + nums[i]// no[i] = max(no[i-1], yes[i-1])if(nums.size()==0)return 0;int sz = nums.size();vector<int> yes(sz);vector<int> no(sz);// init dpyes[0] = nums[0];no[0] = 0;// dpfor(int i = 1; i < sz; i++){yes[i] = no[i-1] + nums[i];no[i] = max(no[i-1], yes[i-1]);}return max(yes[sz-1], no[sz-1]);}
};

5.粉刷房子

link:LCR 091. 粉刷房子 - 力扣（LeetCode）

这是一道三状态dp问题

code

class Solution {
public:int minCost(vector<vector<int>>& costs) {// 每个房间三种状态:红 蓝 绿// r[i], b[i], g[i]:第n个房间为r, b, g时需要最小成本// r[i] = costs[i][0] + min(b[i-1], g[i-1])\// b[i] = costs[i][1] + min(r[i-1], g[i-1])// g[i] = costs[i][2] + min(r[i-1], b[i-1])int n = costs.size();vector<int> r(n), b(n), g(n);// init dpr[0] = costs[0][0];b[0] = costs[0][1];g[0] = costs[0][2];// dpfor(int i = 1; i < n; i++){r[i] = costs[i][0] + min(b[i-1], g[i-1]);b[i] = costs[i][1] + min(r[i-1], g[i-1]);g[i] = costs[i][2] + min(r[i-1], b[i-1]);}return min(min(r[n-1], b[n-1]), g[n-1]);}
};

6.买股票的最佳时机含冷冻期

link:309. 买卖股票的最佳时机含冷冻期 - 力扣（LeetCode）

tips:

// 此问题中，必须要使用至少三种状态，这样才能包含每种可能状态，方便状态转移中推到当前状态。

// 如果只使用一种状态（持有股票）或两种状态（持有股票和不持有股票），都会给状态转移带来不必要麻烦，甚至将时间复杂度提升一个等级

// 你可以尝试在本题中只使用一种/两种状态，这会使状态转移时非常棘手

更正：以上注释掉的部分有误，因为只用两种状态(持有/不持有股票）也可以覆盖dp[i]所有可能情况（和第七题，依旧是下一题状态表示一样），关于冷冻期，调整no[i]刷新策略即可。具体写法见code2-两状态表示

虽然3/2状态都可以正常dp，但是一状态（只有持有状态）就不行了，因为不能覆盖dp[i]所有可能状态，不可状态转移（或者说非常棘手，还会将时间复杂度提升一个等级）

code1-三状态表示

class Solution {
public:int maxProfit(vector<int>& prices) {// f[i][0]:第i天后为可买入状态获得的最大利润 / 手里有股票// f[i][1]：第i天后为可卖出状态获得的最大利润 / 手里没有股票， 没冷冻期// f[i][2]:第i天后是冷冻期状态时获得的最大利润 / 冷冻期vector<vector<int>> f(prices.size(), vector<int>(3, 0));// init dpf[0][0] = -prices[0];f[0][1] = f[0][2] = 0;// dpfor(int i = 1; i < prices.size(); i++){f[i][0] = max(f[i-1][0], f[i-1][1] - prices[i]);f[i][1] = max(f[i-1][1], f[i-1][2]);// 昨天不能是有股票状态， 不然今天就i是冷冻期f[i][2] = f[i-1][0] + prices[i];}int n = prices.size();return max(f[n-1][0], max(f[n-1][1], f[n-1][2]));}
};

code2-两状态表示

class Solution {
public:int maxProfit(vector<int>& prices) {// have[i]:第i天决策后持有股票// no[i]:第i天不决策后持有股票if(prices.size() <= 1)return 0;int n = prices.size();vector<int> have(n+1, 0), no(n+1, 0);// init dphave[0] = -prices[0];no[0] = 0;have[1] = max(-prices[1], -prices[0]);no[1] = max(0, prices[1]-prices[0]);// dpfor(int i = 2; i < n; i++){have[i] = max(have[i-1], no[i-2] - prices[i]);no[i] = max(have[i-1]+prices[i], no[i-1]);}return no[n-1];}
};

7.买股票的最佳时机含手续费

link:714. 买卖股票的最佳时机含手续费 - 力扣（LeetCode）

code

class Solution {
public:int maxProfit(vector<int>& prices, int fee) {// have[i]:第i天决策后有股票// no[i]:第i天决策后没有股票int n = prices.size();vector have(n, 0);vector no(n, 0);// init dphave[0] = -prices[0];no[0] = 0;// dpfor(int i = 1; i < n; i++){have[i] = max(have[i-1], no[i-1] - prices[i]);no[i] = max(no[i-1], have[i-1] + prices[i] - fee);}return no[n-1];}
};

8.买卖股票的最佳时机III

link:123. 买卖股票的最佳时机 III - 力扣（LeetCode）

注意本题是的dp状态是二维的

状态机：

code

class Solution {
public:int maxProfit(vector<int>& prices) {// 二维dp状态， 完全覆盖所有可能状态// have[i][j]: 第i天后， 持有股票，且已经完成了j次交易// no[i][j]: 第i天后， 不持有股票， 且已经完成了j次交易// have[i][j] = max(have[i-1][j], no[i-1][j]);// no[i][j] = max(no[i-1][j], have[i-1][j-1]);#define MAXN 0x3f3f3f3fint n = prices.size();vector<vector<int>> have(n, vector(3, -MAXN));auto no = have;// init dphave[0][0] = -prices[0];no[0][0] = 0;// dpfor(int i = 1; i < have.size(); i++){for(int j = 0; j < have[0].size(); j++){have[i][j] = max(have[i-1][j], no[i-1][j] - prices[i]);no[i][j] = max(no[i-1][j], j-1>=0?have[i-1][j-1] + prices[i]:-MAXN);}}// return ansint ans = 0;for(int cnt = 0; cnt < have[0].size(); cnt++){ans = max(ans, no[n-1][cnt]);}return ans;}
};

9.买卖股票的最佳时机IV

link:188. 买卖股票的最佳时机 IV - 力扣（LeetCode）

和上题III一样，不过2改为k

code

class Solution {
public:int maxProfit(int k, vector<int>& prices) {// 二维dp状态， 完全覆盖所有可能状态// have[i][j]: 第i天后， 持有股票，且已经完成了j次交易// no[i][j]: 第i天后， 不持有股票， 且已经完成了j次交易// have[i][j] = max(have[i-1][j], no[i-1][j]);// no[i][j] = max(no[i-1][j], have[i-1][j-1]);#define MAXN 0x3f3f3f3fint n = prices.size();vector<vector<int>> have(n, vector(k+1, -MAXN));auto no = have;// init dphave[0][0] = -prices[0];no[0][0] = 0;// dpfor(int i = 1; i < have.size(); i++){for(int j = 0; j < have[0].size(); j++){have[i][j] = max(have[i-1][j], no[i-1][j] - prices[i]);no[i][j] = max(no[i-1][j], j-1>=0?have[i-1][j-1] + prices[i]:-MAXN);}}// return ansint ans = 0;for(int cnt = 0; cnt < have[0].size(); cnt++){ans = max(ans, no[n-1][cnt]);}return ans;}
};

四.子数组系列

1.最大子数组和

link:53. 最大子数组和 - 力扣（LeetCode）

tips:因为元素可能是负数，则其序列和不具有单调性，不可使用滑动窗口

code

class Solution {
public:int maxSubArray(vector<int>& nums) {// dp, 子数组系列问题// dp[i]:以i位置结尾的...// dp[i] = num[i] + max(0, dp[i-1]);vector<int> dp(nums.size(), 0);// init dpdp[0] = nums[0];// dpfor(int i = 1; i < nums.size(); i++){dp[i] = nums[i] + max(0, dp[i-1]);}// return ansint ans = dp[0];for(int i = 1; i < dp.size(); i++){ans = max(ans, dp[i]);}return ans;}
};

2.环形子数组的最大和

link:

tip:

本题关键是有环，增添了很多边界情况，使问题变得棘手。

和打架劫舍II一样，我们可以通过分情况讨论消除环的影响，将其变为普通线性结构

两种情况如下：

所以，我们只需求出线性结构时（不成环），最大&最小子数组和即可

本题中，注意nums元素都是负数的情况，此时只返回nums中最大元素即可

code

class Solution {
public:int maxSubarraySumCircular(vector<int>& nums) {// 分情况讨论，转化为线性结构// f[i]:i结尾，（线性结构）非空子数组最大和// g[i]:i结尾，(线性结构)非空子数组最小和// f[i] = nums[i] + max(0, f[i-1]);// g[i] = nums[i] + min(0, g[i-1]); // i >0 && i < n-1int n = nums.size();int sum = 0;for(int i = 0; i < nums.size(); i++) sum+=nums[i];vector<int> f(n);auto g = f;// init dpf[0] = g[0] = nums[0];// dpfor(int i = 1; i < f.size(); i++){f[i] = nums[i] + max(0, f[i-1]);g[i] = nums[i] + min(0, g[i-1]);}// return ans;int ans = nums[0];for(int i = 1; i < f.size(); i++){ans = max(ans, f[i]);if(g[i] != sum) ans = max(ans, sum - g[i]);// 防止g中出现选取所有元素时间（nums都是负数的情况）}return ans;}
};

3.乘积最大子数组

link:152. 乘积最大子数组 - 力扣（LeetCode）

code

class Solution {
public:int maxProduct(vector<int>& nums) {// f[i]:以i结尾的绝对值最大的正数// g[i]:以i结尾的绝对值最大的负数// 这两个状态保证覆盖寻找 数组中成绩罪的的非空连续子数组 的所需值：前最大/最小值int n = nums.size();vector<int> f(n, 0);auto g = f;// init dpf[0] = g[0] = nums[0];// dpfor(int i = 1; i < n; i++){f[i] = max(f[i-1] * nums[i], max(nums[i], g[i-1] * nums[i]));g[i] = min(g[i-1] * nums[i], min(nums[i], f[i-1] * nums[i]));}// return ans;int ans = nums[0];for(int i = 0; i < n; i++){ans = max(ans, f[i]);}return ans;}
};

4.乘积为正数的最长子数组长度

link:1567. 乘积为正数的最长子数组长度 - 力扣（LeetCode）

code

class Solution {
public:int getMaxLen(vector<int>& nums) {// f[i], g[i]:以i结尾的 最长正/负 长度  int n = nums.size();vector<int> f(n, 0);auto g = f;// init dpf[0] = nums[0] > 0 ? 1 : 0;g[0] = nums[0] < 0 ? 1 : 0;if(nums[0] == 0) g[0] = f[0] = 0;// dpfor(int i = 1; i < n; i++){if(nums[i] == 0){g[i] = f[i] = 0;continue;}else if(nums[i] > 0){f[i] = 1 + f[i-1];g[i] = g[i-1]==0 ? 0 : 1 + g[i-1];}else // nums[i] < 0{g[i] = 1 + f[i-1];f[i] = g[i-1]==0 ? 0 : 1 + g[i-1];}}// return ansint ans = 0;for(int i = 0; i < n; i++){ans = max(ans, f[i]);}return ans;}
};

5.最长湍流子数组

link:978. 最长湍流子数组 - 力扣（LeetCode）

code

class Solution {
public:int maxTurbulenceSize(vector<int>& arr) {// dp[i]:以i结尾...if(arr.size() <= 1) return arr.size();int n = arr.size();vector<int> dp(n, 0);// init dpdp[0] = 1;dp[1] = arr[1] != arr[0] ? 2 : 1;int presub = arr[1] - arr[0];// dpfor(int i = 2; i < n; i++){int sub = arr[i] - arr[i-1];if(diff(sub, presub)) dp[i] = dp[i-1] + 1;else dp[i] = sub == 0 ? 1 : 2;presub = sub;}// return ansint ans = 0;for(int i = 0; i < n; i++){ans = max(ans, dp[i]);}return ans;}bool diff(int a, int b)// 是否异号{if(a == 0 || b == 0) return false;return (a > 0) ^ (b > 0);}
};

6.单词拆分

link:139. 单词拆分 - 力扣（LeetCode）

code

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {// dp[i]:以s[i]结尾的s的字串是否可被wordDict拼接而成unordered_set<string> set(wordDict.begin(), wordDict.end());int n = s.size();vector<bool> dp(n, false);// init dpdp[0] = set.count(s.substr(0, 1));// dpfor(int i = 1; i < n; i++){for(int j = i; j >= 0; j--)// j为最后一个单词的起始位置{if((j-1 >= 0 ? dp[j-1] : true) && set.count(s.substr(j, i-j+1))){dp[i] = true;break;}}}// check dpprintf("dp:\n");for(int i = 0; i < n; i++){printf("dp[%d] : %d\n", i, dp[i]?1:0);}// return ansreturn dp[n-1];}
};

7.环绕字符串中唯一的子字符串

link:467. 环绕字符串中唯一的子字符串 - 力扣（LeetCode）

code

class Solution {
public:int findSubstringInWraproundString(string s) {// dp[i]: s[i]结尾的不同非空字串个数中满足条件的不同非空字串// init dpint n = s.size();vector<int> dp(n, 1);// dpfor(int i = 1; i < n; i++){if(s[i]-s[i-1] == 1 || (s[i]=='a' && s[i-1]=='z')) dp[i] = 1 + dp[i-1];else dp[i] = 1;}// 去重int hash[128];memset(hash, 0, sizeof hash);for(int i = 0; i < dp.size(); i++){hash[s[i]] = max(hash[s[i]], dp[i]);}// return ansint ans = 0;for(int i = 0; i < 126; i++){ans += hash[i];}return ans;}
};

五.子序列问题

子序列 & 子数组？

子数组要求连续
子序列不要求连续，但要求相对位置不变

严格递增 & 不严格递增

严格递增：a[i] > a[i-1]
不严格递增：a[i] >= a[i-1]

1.最长递增子序列

link:300. 最长递增子序列 - 力扣（LeetCode）

code

class Solution {
public:int lengthOfLIS(vector<int>& nums) {// 动态规划// dp[i]表示：以nums[i]为最后一个元素的最长递增子序列vector<int> dp = vector<int>(nums.size() + 5, 1);// init dpdp[0] = 1;// dpfor(int i = 1; i < nums.size(); i++){for(int j = 0; j < i; j++){if(nums[j] < nums[i]) dp[i] = max(dp[i], dp[j] + 1);}}int ans = dp[0];for(int i = 0; i < nums.size(); i++){ans = max(ans, dp[i]);}return ans;}
};

2.摆动序列

link:376. 摆动序列 - 力扣（LeetCode）
code

class Solution {
public:int wiggleMaxLength(vector<int>& nums) {// f[i]:以nums[i]结尾的， 倒一减倒二大于0的， 最长子序列长度// g[i]:以nums[i]结尾的， 倒一减倒二小于0的， 最长子序列长度if(nums.size() <= 1) return nums.size();int n = nums.size();vector<int> f(n, 1);auto g = f;// init dpf[1] = nums[1] - nums[0] > 0 ? 2 : 1;// 上升结尾g[1] = nums[1] - nums[0] < 0 ? 2 : 1;// dpfor(int i = 2; i < n; i++){for(int j = 0; j < i; j++){int sub = nums[i] - nums[j];if(sub > 0){f[i] = max(g[j] + 1, f[i]);}else if(sub < 0){g[i] = max(f[j] + 1, g[i]);}}}// return ans;int ans = 0;for(int i = 0; i < n; i++){ans = max(ans, max(f[i], g[i]));}return ans;}
};

3.最长递增子序列的个数

link:673. 最长递增子序列的个数 - 力扣（LeetCode）

code

class Solution {
public:int findNumberOfLIS(vector<int>& nums) {// dp[i][0]:nums[i]结尾的， 最长递增子序列的 长度// dp[i][1]:nums[i]结尾的， 最长递增子序列的 个数if(nums.size() <= 1) return nums.size();int n = nums.size();vector<vector<int>> dp(n, vector<int>(2, 1));// init dp// dpfor(int i = 1; i < n; i++){for(int j = 0; j < i; j++){if(nums[i] > nums[j]){if(dp[j][0] + 1 == dp[i][0]) dp[i][1]+=dp[j][1];else if(dp[j][0] + 1 > dp[i][0]){dp[i][0] = dp[j][0] + 1;dp[i][1] = dp[j][1];}}}}// return ans;int maxlen = 1;for(int i = 0; i < dp.size(); i++){maxlen = max(maxlen, dp[i][0]);}int cnt = 0;for(int i = 0; i < dp.size(); i++){if(dp[i][0] == maxlen) cnt += dp[i][1];}return cnt;}
};

4.最长数对链

link:646. 最长数对链 - 力扣（LeetCode）

code

class Solution {
public:int findLongestChain(vector<vector<int>>& pairs) {// 先排序 创造单调性 为使用dp创造条件// dp[i]:排序后， 以pairs[i]结尾的， 最长数对链的长度sort(pairs.begin(), pairs.end(), [](vector<int>& vc1, vector<int>& vc2){return vc1[0] < vc2[0];});int n = pairs.size();vector<int> dp(n, 1);// init dp// dpfor(int i = 1; i < n; i++){for(int j = 0; j < i; j++){if(pairs[j][1] < pairs[i][0]){dp[i] = max(dp[i], dp[j] + 1);}}}// return ans;return dp[n-1];}
};

5.最长定差子序列

link:1218. 最长定差子序列 - 力扣（LeetCode）

key: 哈希表代替遍历查找arr[i]-d结尾的满足题意的子序列的最大长度，降低时间复杂度

code

class Solution {
public:int longestSubsequence(vector<int>& arr, int d) {// dp[i]:以arr[i]结尾的， 最长等差（diff)子序列int n = arr.size();vector<int> dp(n, 1);unordered_map<int, int> hash;// init dp// dpfor(int i = 0; i < n; i++){// 使用hash表，避免遍历查找arr[i]-d结尾子序列最大长度dp[i] = hash[arr[i]-d] + 1;hash[arr[i]] = max(hash[arr[i]], dp[i]);}// return ans;int ans = 1;for(int i = 0; i < n; i++){ans = max(ans, dp[i]);}return ans;}
};

6.最长的斐波那契子序列长度

link:873. 最长的斐波那契子序列的长度 - 力扣（LeetCode）

tip:

注意dp时的顺序，先列后行

哈希表避免遍历查询元素下标

code

class Solution {
public:int lenLongestFibSubseq(vector<int>& arr) {// 二维dp// dp[i][j]:arr[i], arr[j]为最后两元素// 注意初始化顺序，先列后行int n = arr.size();vector<vector<int>> dp(n, vector<int>(n, 2));unordered_map<int, int> map;// 值：下标// init dpdp[0][0] = 1;for(int i = 0 ; i < n; i++){map[arr[i]] = i;}// dpint ans = 2;for(int j = 2; j < dp.size(); j++){for(int i = 1; i < j ; i++){int sub = arr[j] - arr[i];if(map.count(sub) && sub < arr[i]) dp[i][j] = 1 + dp[map[sub]][i];else dp[i][j] = 2;ans = max(ans, dp[i][j]);}}// return ansprintf("ans = %d\n", ans);return ans >= 3 ? ans : 0;}
};

7.最长等差数列

link:1027. 最长等差数列 - 力扣（LeetCode）

tips:

和上题最长斐波那契数列很类似
如果只用dp[i]表示以nums[i]结尾的最长等差子序列的长度，写不出状态转移方程，因为缺少了dp[j]对应的差值，所以不能判断dp[i]连接在dp[j]后是否为等差数列
所以，我们要用二维dp[i][j]表示:最后两项为nums[i],nums[j]的最长子序列长度
为什么不用dp[i], len[i]代替dp[i][j]?信息还是不充足，写不出状态转移方程

&:注意初始化顺序，只有先i后j才能同时正确地动态初始化hash

code

class Solution {
public:int longestArithSeqLength(vector<int>& nums) {int n = nums.size();vector<vector<int>> dp(n, vector<int>(n, 2));unordered_map<int, int> hash;// for(int i = 0; i < n; i++) hash[nums[i]] = i;// init dp// dpint ans = 2;for(int i = 0; i < n; i++){for(int j = i + 1; j < n; j++){int sub = nums[j] - nums[i];int target = nums[i] - sub;if(hash.count(target) && hash[target] < i){dp[i][j] = dp[hash[target]][i] + 1;ans = max(ans, dp[i][j]);}}hash[nums[i]] = i;// 只有dp顺序为先i后j，才能正确初始化hash}// return ansreturn ans;}
};

8.等差数列划分II-子序列

link:446. 等差数列划分 II - 子序列 - 力扣（LeetCode）

code

class Solution {
public:int numberOfArithmeticSlices(vector<int>& nums) {// dp[i][j]:以nums[i], nums[j]结尾的等差子序列的 个数using ll = long long int;int n = nums.size();vector<vector<int>> dp(n, vector<int>(n, 0));unordered_map<ll, vector<int>> hash;for(int i = 0; i < n; i++) hash[nums[i]].push_back(i);// init dpint ans = 0;for(int j = 2; j < n; j++){for(int i = 1; i < j; i++){ll a = 2 * ll(nums[i]) - nums[j];for(int idx:hash[a]){if(idx < i) dp[i][j] += dp[idx][i] + 1;}ans += dp[i][j];}}return ans;}
};

六.回文串问题

1.回文子串

link:647. 回文子串 - 力扣（LeetCode）

code

class Solution {
public:int countSubstrings(string s) {// dp[i][j]:s[i:j]是否为回文串int n = s.size();vector<vector<int>> dp(n, vector<int>(n, 0));// dp// 由下向上dpfor(int i = n - 1; i >= 0; i--){for(int j = i; j < n; j++){if(s[i] != s[j]){dp[i][j] = false;continue;}if(i + 1 < j - 1){dp[i][j] = dp[i+1][j-1];}else{dp[i][j] = true;}}}// return ans;int ans = 0;for(int i = 0; i < n; i++){for(int j = i; j < n; j++){ans += dp[i][j];}}return ans;}
};

2.最长回文字串

link:5. 最长回文子串 - 力扣（LeetCode）

code

class Solution {
public:string longestPalindrome(string s) {// dp[i][j]:s[i][j]是否为回文字串int maxlen = 0;int bgn = 0;int n = s.size();vector<vector<int>> dp(n, vector<int>(n, 0));// dpfor(int i = n; i >= 0; i--){for(int j = i; j < n; j++){if(s[i] == s[j]){dp[i][j] = i + 1 < j - 1 ? dp[i+1][j-1] : true;}else dp[i][j] = false;int len = j - i + 1;if(dp[i][j] && len > maxlen){maxlen = len;bgn = i;}}}printf("bgn = %d, maxlen = %d\n", bgn, maxlen);return s.substr(bgn, maxlen);}
};

3.分割回文串

link:1745. 分割回文串 IV - 力扣（LeetCode）

code

class Solution {
public:bool checkPartitioning(string s) {// dp[i][j]:s[i:j]是否为回文串int n = s.size();vector<vector<bool>> dp(n, vector<bool>(n, false));// dpfor(int i = n - 1; i >= 0; i--){for(int j = i; j < n; j++){if(s[i] == s[j]){dp[i][j] = i + 1 < j - 1 ? dp[i+1][j-1] : true;}}}// return ans// 判断s[0:i], s[i+1:j], s[j+1:]是否为回文for(int i = 0; i < n - 2; i++){for(int j = i + 1; j < n - 1; j++){if(dp[0][i] && dp[i+1][j] && dp[j+1][n-1]){return true;}}   }return false;}
};

5.分割回文串II

link:132. 分割回文串 II - 力扣（LeetCode）

code

class Solution {
public:int minCut(string s) {#define INF 0x3f3f3f3fint n = s.size();vector<vector<bool>> huiwen(n, vector<bool>(n, false));// dpfor(int i = n - 1; i >= 0; i--){for(int j = i; j < n; j++){if(s[i] == s[j]){huiwen[i][j] = i + 1 < j - 1 ? huiwen[i+1][j-1] : true;}}}// dpvector<int> dp(n, INF);// dp[i]:s[:i]最少分割数for(int i = 0; i < n; i++){if(huiwen[0][i]){dp[i] = 0;continue;}for(int j = 1; j <= i; j++)// dp[j:i]是最后一个回文串{if(huiwen[j][i]){dp[i] = min(dp[i], dp[j-1] + 1);}}}return dp[n-1];}
};

七.两个数组的dp问题

1.最长公共子序列

这是非常非常经典的一道两数组dp问题，很有借鉴/学习意义。

link:1143. 最长公共子序列 - 力扣（LeetCode）

code

class Solution {
public:int longestCommonSubsequence(string text1, string text2) {// dp[i][j]:text1[:i], text2[:j]最长公共子序列int n = text1.size();int m = text2.size();vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));// 空串方便初始化text1 = " " + text1;text2 = " " + text2;// 保证坐标对应// dpfor(int i = 1; i <= n; i++){for(int j = 1; j <=m; j++){if(text1[i] == text2[j])dp[i][j] = dp[i-1][j-1] + 1;elsedp[i][j] = max(dp[i-1][j], dp[i][j-1]);}}return dp[n][m];}
};

tips:

字符串/子序列中，空串是有意义的，而且加上空串也会方便初始化，防止越界

2.不相交的线

其实就是最长公共子序列

link:1035. 不相交的线 - 力扣（LeetCode）

code

class Solution {
public:int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {// 就是求最长公共子序列// dp[i][j]:nums1[:i], nums2[:j]最大连线数int n = nums1.size();int m = nums2.size();vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));nums1.insert(nums1.begin(), -1);nums2.insert(nums2.begin(), -2);// 保证下标对应// dpfor(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){if(nums1[i] == nums2[j])dp[i][j] = dp[i-1][j-1] + 1;elsedp[i][j] = max(dp[i-1][j], dp[i][j-1]);}}return dp[n][m];}
};

3.不同的子序列

link:115. 不同的子序列 - 力扣（LeetCode）

key:

空串往往是有意义的，一定要考虑空串情况

init dp时，dp[i][0] = 1，代表s[:i]中有一个" "

code

class Solution {
public:int numDistinct(string s, string t) {// dp[i][j]:在s[:i]中， t[j]出现的个数#define MOD (int(1e9 + 7))int n = s.size();int m = t.size();vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));s = " " + s;t = " " + t;// 下标对应// init dp 注意， 空串也是有意义的， dp[i][0] = 1, 代表s[:i]中有一个" "dp[0][0] = 1;for(int i = 1; i <= n; i++) dp[i][0] = 1;// dpfor(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){   // 求s[:i]中， 多少次t[:j]if(s[i] == t[j]) dp[i][j] = (dp[i-1][j-1] + dp[i-1][j]) % MOD;// 以s[:i]结尾的t[:j]个数 + s[:i-1]内t[:j]个数elsedp[i][j] = dp[i-1][j] % MOD;// s[:i-1]内t[:j]个数}}return dp[n][m];}
};

4.通配符匹配

link:44. 通配符匹配 - 力扣（LeetCode）

tips:

本题关键，p[j]=='*'时状态转移方程

本题有两种方法推导出上述答案(dp[i][j] = dp[i-1][j] || dp[i][j-1]):数学法和实际分析法

code

class Solution {
public:bool isMatch(string s, string p) {// dp[i][j]:s[:i]是否可以匹配p[:j]// key:p[j]=="*"时状态转移方程int n = s.size();int m = p.size();vector<vector<int>> dp(n + 1, vector<int>(m + 1, false));s = " " + s;p = " " + p;// init dpdp[0][0] = true;// 空串可以匹配空串for(int i = 1; i <= m; i++) // *可匹配空串{if(p[i]=='*'){dp[0][i] = true;}else break;}// dp// for(int i = 1; i <= n; i++)for(int j = 1; j <= m; j++){// for(int j = 1; j <= m; j++)for(int i = 1; i <= n; i++){if(p[j] == '*') dp[i][j] = dp[i][j-1] || dp[i-1][j];else if(p[j] == s[i] || p[j] == '?')dp[i][j] = dp[i-1][j-1];else dp[i][j] = false; p[j]不是？*且p[j] != s[i]:一定不能匹配}}return dp[n][m];}
};

5.正则表达式匹配

link:10. 正则表达式匹配 - 力扣（LeetCode）

和上题差不多，只是*匹配规则有变化，导致p[j]==‘*’时状态转移方程有些许小变化，但两题思路/做法相同

key:

dp init

p[j] == '*'时状态转移方程

code

class Solution {
public:bool isMatch(string s, string p) {// dp[i][j]: p[:j]能否匹配s[:i]int n = s.size();int m = p.size();vector<vector<bool>> dp(n + 1, vector<bool>(m + 1, false));s = " " + s;p = " " + p;// 下标对齐， 考虑空串// init dpdp[0][0] = true;// 空串可以匹配空串// p = ".*a*b*?*.........."时， 可匹配s=""(空)for(int j = 2; j <= m; j += 2) {if(p[j] == '*') dp[0][j] = true;else break;}// dpfor(int j = 1; j <= m; j++){for(int i = 1; i <= n; i++){if (p[j] == '*') dp[i][j] = dp[i][j-2] || ((p[j-1] == '.' || p[j-1] == s[i]) && dp[i-1][j]);// key,分两种情况，*匹配0个前字符(dp[i][j-2])/// *匹配1至多个前字符((p[j-1] == '.' || p[j-1] == s[i]) &&dp[i-1][j])else if(p[j] == s[i] || p[j] == '.') dp[i][j] = dp[i-1][j-1];else dp[i][j] = false;}}return dp[n][m];}
};

6.交错字符串

link:97. 交错字符串 - 力扣（LeetCode）

本题比较容易退出状态表示和状态转移方程

code

class Solution {
public:bool isInterleave(string s1, string s2, string s3) {// dp[i][j]:s1[:i], s2[:j]是否可以交错形成s3[:i+j]if(s1.size() + s2.size() != s3.size()) return false;int n = s1.size();int m = s2.size();s1 = " " + s1;s2 = " " + s2;s3 = " " + s3;vector<vector<bool>> dp(n + 1, vector(m + 1, false));// init dpdp[0][0] = true;for(int i = 1; i <= n; i++) {if(s1[i] == s3[i]) dp[i][0] = true;else break;}for(int j = 1; j <= m; j++) {if(s2[j] == s3[j]) dp[0][j] = true;else break;}// dpfor(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){bool ret1 = s1[i]==s3[i+j] && dp[i-1][j];bool ret2 = s2[j]==s3[i+j] && dp[i][j-1];dp[i][j] = ret1 || ret2;}}return dp[n][m];}
};

7.两个字符串的最小ASCII删除和

link:712. 两个字符串的最小ASCII删除和 - 力扣（LeetCode）

key:

正难则反，将求最小删除ASCII值转化为求公共子序列最大ASCII值

状态转移时，按照公共子序列最后一个字符是否有s1[i]和s2[j]两个字符，分情况即可

code

class Solution {
public:int minimumDeleteSum(string s1, string s2) {// 正难则反， 求删除字符ASCII最小和， 就是求公共子序列的最大ASCII和// dp[i][j]:s1[:i], s2[:j]公共子序列的最大ASCII// 状态转移时， 根据公共子序列是否包含s1[i],s2[j]字符,分情况即可// 或者说， 公共子序列最后一个字符，是否是s1[i],s2[j]int n = s1.size(); int m = s2.size();s1 = " " + s1;s2 = " " + s2;vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));// init dp// 空串情况都是0， 创建dp时已经初始化// dpfor(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){if (s1[i] == s2[j]) dp[i][j] = dp[i-1][j-1] + s1[i];// s1[i],s2[j]都能用到else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);// s1[i],s2[j]至少一个用不到}}// return ans;int sum1 = 0, sum2 = 0;for(int i = 1; i <= n; i++) sum1 += s1[i];for(int j = 1; j <= m; j++) sum2 += s2[j];return sum1 + sum2 - 2 * dp[n][m];}
};

8.最长重复子数组

link:718. 最长重复子数组 - 力扣（LeetCode）

tips:
这是一道比较简单的双数组dp问题

注意求子数组时的dp状态表示，dp[i][j]一定表示的是以nums1[i], nums2[j]为结尾的子数组。

这点不同于子序列，因为子序列不要求连续，所以子序序列问题的dp状态表示不要求也不能要求指定结尾

code

class Solution {
public:int findLength(vector<int>& nums1, vector<int>& nums2) {// 由于本题是求子数组长度，子数组要求连续，所以dp[i][j]一定要保证是结尾状态， 不能像子序列一样的区间状态；// dp[i][j]:以nums1[i], nums2[j]结尾的，最长子数组的长度int n = nums1.size();int m = nums2.size();nums1.insert(nums1.begin(), -1);nums2.insert(nums2.begin(), -2);vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));// dpint ans = 0;for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){if(nums1[i] == nums2[j]){dp[i][j] = dp[i-1][j-1] + 1;}ans = max(ans, dp[i][j]);}}return ans;}
};