1137. 第 N 个泰波那契数 - 力扣（LeetCode）
class Solution {
public:
int tribonacci(int n) {
if(n==0) return 0;
if(n==1||n==2) return 1;
vector<int> dp(4);
//初始化
dp[0]=0; dp[1]=1; dp[2]=1;
for(int i=3;i<n+1;i++){//滚动数组优化需要循环
dp[i%4]=dp[(i-1)%4]+dp[(i-2)%4]+dp[(i-3)%4];
}
return dp[n%4];
}
};面试题 08.01. 三步问题 - 力扣（LeetCode）
class Solution {
public:
int waysToStep(int n) {
const int MOD=1e9+7;
if(n==1) return 1;
if(n==2) return 2;
if(n==3) return 4;
int a=1; int b=2; int c=4; int d=0;
for(int i=4;i<=n;i++){
d=((a+b)%MOD+c)%MOD;
a=b; b=c; c=d;
}
return d;
}
};class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n=cost.size();
if(n<=1) return 0;
vector<int> dp(n+1);
dp[0]=0;
dp[1]=0;
for(int i=2;i<n+1;i++){
dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
}
return dp[n];
}
};class Solution {
public:
int numDecodings(string s) {
int n=s.size();
vector<int> dp(n,0);
dp[0]=s[0]!='0';
if(n==1) return dp[0];
//初始化下标1
if('0'<s[1]&&s[1]<='9') dp[1]+=dp[0];
int a=s[0]-'0'; int b=s[1]-'0';
if(10<=a*10+b&&a*10+b<=26) dp[1]++;
for(int i=2;i<n;i++){
if('0'<s[i]&&s[i]<='9') dp[i]+=dp[i-1];
int c=s[i-1]-'0'; int d=s[i]-'0';
if(10<=c*10+d&&c*10+d<=26&&dp[i-2]) dp[i]+=dp[i-2];
}
for(int &val:dp){
cout<<val<<endl;
}
return dp[n-1];
}
};class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> dp(m+1,vector<int>(n+1,0));
dp[1][0]=1;
for(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];
}
};class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m=obstacleGrid.size(); int n=obstacleGrid[0].size();
vector<vector<int>> dp(m+1,vector<int>(n+1,0));
dp[1][0]=1;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(obstacleGrid[i-1][j-1]!=1)
dp[i][j]=dp[i-1][j]+dp[i][j-1];
}
}
return dp[m][n];
}
};LCR 166. 珠宝的最高价值 - 力扣（LeetCode）
class Solution {
public:
int jewelleryValue(vector<vector<int>>& frame) {
int m=frame.size(); int n=frame[0].size();
vector<vector<int>> dp(m+1,vector<int>(n+1,0));
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
dp[i][j]=max(dp[i-1][j],dp[i][j-1])+frame[i-1][j-1];
}
}
return dp[m][n];
}
};class Solution {
public:
int minFallingPathSum(vector<vector<int>>& matrix) {
//建表
int m=matrix.size(); int n=matrix[0].size();
vector<vector<int>> dp(m+1,vector<int>(n+2,INT_MAX));
//初始化
for(int i=0;i<=n+1;i++){
dp[0][i]=0;
}
//填表
for(int i=1;i<=m;i++){
for(int j=1;j<n+1;j++){
dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j],dp[i-1][j+1]))+matrix[i-1][j-1];//***1***注意dp的下标和数据数组的下标对应起来,**2**初始化要满足依靠初始的状态填表正确
}
}
int ret=INT_MAX;
for(int i=1;i<n+1;i++){
ret=min(dp[m][i],ret);
}
return ret;
}
};class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
//建表
int m=grid.size(); int n=grid[0].size();
vector<vector<int>> dp(m+1,vector<int>(n+1,INT_MAX));
//初始化
dp[0][1]=0;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i-1][j-1];
}
}
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
cout<<dp[i][j]<<" ";
}
cout<<endl;
}
return dp[m][n];
}
};class Solution {
public:
int calculateMinimumHP(vector<vector<int>>& dungeon) {
int m=dungeon.size(); int n=dungeon[0].size();
vector<vector<int>> dp(m+1,vector<int>(n+1,INT_MAX));
dp[m][n-1]=1;//依题意是 1，不是0;
for(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])-dungeon[i][j];
dp[i][j]=dp[i][j]<1?1:dp[i][j];//状态表示：骑士的血无法小于1
}
}
return dp[0][0]<1?1:dp[0][0];
}
};class Solution {
public:
int massage(vector<int>& nums) {
int n=nums.size();
if(n==0) return 0;
vector<int> f(n);
vector<int> g(n);
f[0]=nums[0];
for(int i=1;i<n;i++){
g[i]=max(f[i-1],g[i-1]);
f[i]=g[i-1]+nums[i];
// cout<<g[i]<<" "<<f[i]<<endl;
}
return g[n-1]>f[n-1]?g[n-1]:f[n-1];
}
};class Solution {
public:
int rob(vector<int>& nums) {
int n=nums.size();
return max(nums[0]+rob_1(nums,2,n-2),rob_1(nums,1,n-1));
}
int rob_1(vector<int>& nums,int left,int right){
if(left>right) return 0;//**1**数据不满足范围，那么需要返回0
int n=nums.size();
vector<int> f(n);
vector<int> g(n);
f[left]=nums[left];
for(int i=left+1;i<=right;i++){
g[i]=max(g[i-1],f[i-1]);
f[i]=g[i-1]+nums[i];
}
return g[right]>f[right]?g[right]:f[right];
}
};class Solution {
public:
int deleteAndEarn(vector<int>& nums) {
int hash[10001]={0};
for(int &val:nums){
hash[val]+=val;
}
int f[10001];
int g[10001];
f[0]=hash[0];
for(int i=1;i<10001;i++){
g[i]=max(g[i-1],f[i-1]);
f[i]=g[i-1]+hash[i];
}
return g[10000]>f[10000]?g[10000]:f[10000];
}
};class Solution {
public:
int minCost(vector<vector<int>>& costs) {
int m=costs.size(); int n=costs[0].size();
vector<vector<int>> dp(m+1,vector<int>(3,0));
for(int i=1;i<=m;i++){
dp[i][0]=min(dp[i-1][1],dp[i-1][2])+costs[i-1][0];//***1***初始化要满足递推为正确
dp[i][1]=min(dp[i-1][0],dp[i-1][2])+costs[i-1][1];//***2***下标要映射正确
dp[i][2]=min(dp[i-1][1],dp[i-1][0])+costs[i-1][2];
}
int ret=INT_MAX;
for(int i=0;i<3;i++){
ret=min(ret,dp[m][i]);
}
return ret;
}
};714. 买卖股票的最佳时机含手续费 - 力扣（LeetCode）
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
const int n=prices.size();
int f[n]; int g[n];
f[0]=-prices[0]; g[0]=0;
for(int i=1;i<n;i++){
f[i]=max(g[i-1]-prices[i],f[i-1]);
g[i]=max(f[i-1]+prices[i]-fee,g[i-1]);
}
return g[n-1];
}
};123. 买卖股票的最佳时机 III - 力扣（LeetCode）
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n=prices.size();
int INF=0x3f3f3f3f;
vector<vector<int>> f(n,vector<int>(3,-INF));
vector<vector<int>> g(n,vector<int>(3,-INF));
f[0][0]=-prices[0]; g[0][0]=0;//g[0][0],j=0表示初始状态处于无股票状态，没有买入和卖出，f[0][0];j=0表示第一次买入
for(int i=1;i<n;i++){
for(int j=0;j<3;j++){
f[i][j]=max(f[i-1][j],g[i-1][j]-prices[i]);
g[i][j]=g[i-1][j];
if(j-1>=0)
g[i][j]=max(g[i-1][j],f[i][j-1]+prices[i]);
}
}
int ret=0;
for(int i=0;i<3;i++){
ret=max(ret,g[n-1][i]);
}
return ret;
}
};188. 买卖股票的最佳时机 IV - 力扣（LeetCode）
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
int n=prices.size();
int INF=0x3f3f3f3f;
//优化；
k=min(k,n/2);//最多交易n/2次
vector<vector<int>> f(n,vector<int>(k+1,-INF));
vector<vector<int>> g(n,vector<int>(k+1,-INF));
f[0][0]=-prices[0]; g[0][0]=0;
for(int i=1;i<n;i++){//***2***从第2天开始
for(int j=0;j<k+1;j++){
f[i][j]=max(f[i-1][j],g[i-1][j]-prices[i]);
g[i][j]=g[i-1][j];
if(j-1>=0)
g[i][j]=max(g[i-1][j],f[i-1][j-1]+prices[i]);
}
}
int ret=0;
for(int i=0;i<k+1;i++){
ret=max(ret,g[n-1][i]);
}
return ret;
}
};class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n=nums.size();
//建表
vector<int> dp(n+1,0);
const int INF=0x3f3f3f3f;
int ret=-INF;
for(int i=1;i<=n;i++){
dp[i]=max(nums[i-1],dp[i-1]+nums[i-1]);
ret=max(ret,dp[i]);
}
return ret;
}
};class Solution {
public:
int maxSubarraySumCircular(vector<int>& nums) {
int n=nums.size();
vector<int> f(n+1);
vector<int> g(n+1);
int fmax=INT_MIN; int gmin=INT_MAX; int sum=0;//用来标记全为负数的情况
for(int i=1;i<=n;i++){
int x=nums[i-1];
f[i]=max(f[i-1]+nums[i-1],nums[i-1]);
fmax=max(fmax,f[i]);
g[i]=min(g[i-1]+nums[i-1],nums[i-1]);
gmin=min(gmin,g[i]);
sum+=x;
}
return sum==gmin?fmax:max(fmax,sum-gmin);
}
};class Solution {
public:
int maxProduct(vector<int>& nums) {
int n=nums.size();
vector<int> f(n+1);
vector<int> g(n+1);
//**1**初始化
f[0]=1; g[0]=1;
int ret=INT_MIN;
for(int i=1;i<=n;i++){
f[i]=max(nums[i-1],max(f[i-1]*nums[i-1],g[i-1]*nums[i-1]));
g[i]=min(nums[i-1],min(f[i-1]*nums[i-1],g[i-1]*nums[i-1]));
ret=max(ret,f[i]);
}
return ret;
}
};1567. 乘积为正数的最长子数组长度 - 力扣（LeetCode）
class Solution {
public:
int getMaxLen(vector<int>& nums) {
int n=nums.size();
vector<int> f(n+1);
vector<int> g(n+1);
int ret=INT_MIN;
for(int i=1;i<n+1;i++){
if(nums[i-1]==0){//**3**比较符号不要写成=
f[i]=0; g[i]=0;
}else if(nums[i-1]<0){
f[i]=g[i-1]==0?0:g[i-1]+1;//**1**注意逻辑关系：负数*负数=正数
g[i]=f[i-1]+1;//正数*负数=负数
}else if(nums[i-1]>0){
f[i]=f[i-1]+1;
g[i]=g[i-1]==0?0:g[i-1]+1;
}
cout<<f[i]<<" "<<g[i]<<endl;
ret=max(ret,f[i]);
}
return ret;
}
};class Solution {
public:
int numberOfArithmeticSlices(vector<int>& nums) {
int n=nums.size();
vector<int> dp(n);
int sum=0;
for(int i=2;i<n;i++){
dp[i]=nums[i]+nums[i-2]==2*nums[i-1]?dp[i-1]+1:0;
sum+=dp[i];
}
return sum;
}
};class Solution {
public:
int maxTurbulenceSize(vector<int>& arr) {
int n=arr.size();
vector<int> f(n,1);
vector<int> g(n,1);
int ret=1
;
for(int i=1;i<n;i++){
if(arr[i]>arr[i-1]){
f[i]=g[i-1]+1;
}else if(arr[i]<arr[i-1]){
g[i]=f[i-1]+1;
}
ret=max(ret,max(g[i],f[i]));
}
return ret;
}
};class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> hash;
for(int i=0;i<wordDict.size();i++){
hash.insert(wordDict[i]);
}
int n=s.size();
vector<bool> dp(n+1,false);
dp[0]=true;
for(int i=1;i<n+1;i++){
for(int j=0;j<i;j++){
// cout<<s.substr(j,i-j)<<" ";//**1**对应首位下标改变,长度不变。
if(dp[j]&&hash.count(s.substr(j,i-j)))
dp[i]=true;
cout<<endl;
}
}
return dp[n];
}
};467. 环绕字符串中唯一的子字符串 - 力扣（LeetCode）
class Solution {
public:
int findSubstringInWraproundString(string s) {
int n=s.size();
vector<int> dp(n,1);
for(int i=1;i<n;i++)
if(s[i]==s[i-1]+1||(s[i]=='a'&&s[i-1]=='z'))
dp[i]=dp[i-1]+1;
int hash[26];
for(int i=0;i<n;i++){
hash[s[i]-'a']=max(hash[s[i]-'a'],dp[i]);
}
int sum=0;
for(int i=0;i<26;i++){
sum+=hash[i];
}
return sum;
}
};class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n=nums.size();
vector<int> dp(n,1);
int ret=1;
for(int i=1;i<n;i++){
for(int j=0;j<i;j++){
if(nums[i]>nums[j])
dp[i]=max(dp[i],dp[j]+1);
}
ret=max(ret,dp[i]);
}
return ret;
}
};class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int n=nums.size();
vector<int> g(n,1);
vector<int> f(n,1);
int ret=1;
for(int i=1;i<n;i++){
for(int j=0;j<i;j++){
if(nums[i]>nums[j]) f[i]=max(g[j]+1,f[i]);
if(nums[i]<nums[j]) g[i]=max(f[j]+1,g[i]);
}
ret=max(ret,max(g[i],f[i]));
}
return ret;
}
};673. 最长递增子序列的个数 - 力扣（LeetCode）
class Solution {
public:
int findNumberOfLIS(vector<int>& nums) {
int n=nums.size();
vector<int> len(n,1),count(n,1);
int retlen=1; int retcount=1;
for(int i=1;i<n;i++){
for(int j=0;j<i;j++){
if(nums[i]>nums[j]){
if(len[j]+1==len[i]){
count[i]+=count[j];
}else if(len[j]+1>len[i]){
len[i]=len[j]+1;
count[i]=count[j];
}
}
}
if(retlen<len[i]){
retlen=len[i]; retcount=count[i];
}else if(retlen==len[i]){
retcount+=count[i];
}
}
return retcount;
}
};class Solution {
public:
int findLongestChain(vector<vector<int>>& pairs) {
sort(pairs.begin(),pairs.end(),[](vector<int> a,vector<int> b){
return a[0]<b[0]||(a[0]==b[0]&&a[1]<b[1]);
});
int n=pairs.size();
int ret=1;
vector<int> dp1(n,1);
for(int i=1;i<n;i++){
for(int j=0;j<i;j++){
if(pairs[i][0]>pairs[j][1]) dp1[i]=dp1[j]+1;
}
ret=max(dp1[i],ret);
}
return ret;
}
};class Solution {
public:
int longestSubsequence(vector<int>& arr, int difference) {
int n=arr.size();
unordered_map<int,int> hash;
hash[arr[0]]=1;
int ret=1;
for(int i=1;i<n;i++){
hash[arr[i]]=hash[arr[i]-difference]+1;//**1**等差数组没有前缀，也要插入hash表中
ret=max(ret,hash[arr[i]]);
}
return ret;
}
};873. 最长的斐波那契子序列的长度 - 力扣（LeetCode）
class Solution {
public:
int lenLongestFibSubseq(vector<int>& arr) {
int n=arr.size();
unordered_map<int,int> hash;
for(int i=0;i<n;i++){
hash[arr[i]]=i;
}
vector<vector<int>> dp(n,vector<int>(n,2));
int ret=2;
for(int i=2;i<n;i++){
for(int j=1;j<i;j++){
int a=arr[i]-arr[j];
if(a<arr[j]&&hash.count(a)){
dp[j][i]=dp[hash[a]][j]+1;
}
ret=max(ret,dp[j][i]);
}
}
return ret<3?0:ret;
}
};class Solution {
public:
int longestArithSeqLength(vector<int>& nums) {
int n=nums.size();
unordered_map<int,int> hash;
// hash[nums[0]]=0; hash[nums[1]]=1;
hash[nums[0]]=0;
vector<vector<int>> dp(n,vector<int>(n,2));
int ret=2;//任意两个数都可以构成等差数列
for(int j=1;j<n;j++){
for(int i=j+1;i<n;i++){
int a=2*nums[j]-nums[i];//a可能有多个值,我们必须找到最右端的值，才是最大的，
if(hash.count(a)){
dp[j][i]=dp[hash[a]][j]+1;
}
ret=max(dp[j][i],ret);
// cout<<dp[j][i]<<" ";
}
hash[nums[j]]=j;
// cout<<endl;
}
return ret;
}
};446. 等差数列划分 II - 子序列 - 力扣（LeetCode）
class Solution {
public:
int numberOfArithmeticSlices(vector<int>& nums) {
int n=nums.size();
unordered_map<long long,vector<int>> hash;//**2** long long因为推导等差数组前的值需要2*nums[j].
vector<vector<int>> dp(n,vector<int>(n,0));
for(int i=0;i<n;i++){
hash[nums[i]].push_back(i);
}
int sum=0;
for(int i=2;i<n;i++){
for(int j=1;j<i;j++){
long long a=(long long)2*nums[j]-nums[i];
if(hash.count(a)){//***1**必须要先寻找，hash[a],相当于插入了
for(int k:hash[a]){
if(k<j) dp[j][i]+=dp[k][j]+1;
else break;
cout<<k<<" ";
}
}
sum+=dp[j][i];
}
}
return sum;
}
};class Solution {
public:
int countSubstrings(string s) {
int n=s.size();
vector<vector<bool>> dp(n,vector<bool>(n,false));
int ret=0;
for(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?dp[i+1][j-1]:true;
}else{
dp[i][j]=false;
}
if(dp[i][j]==true) ret++;
}
}
return
}
};class Solution {
public:
string longestPalindrome(string s) {
int n=s.size();
vector<vector<bool>> dp(n,vector<bool>(n,0));
int len=0; int begin=0;
for(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?dp[i+1][j-1]:true;
}
if(dp[i][j]==true&&j-i+1>len){
len=j-i+1; begin=i;
}
}
}
return s.substr(begin,len);
}
};class Solution {
public:
bool checkPartitioning(string s) {
int n=s.size();
vector<vector<bool>> dp(n,vector<bool>(n,false));
for(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?dp[i+1][j-1]:true;
}
}
}
for(int j=1;j<n;j++){
for(int i=j+1;i<n;i++){
if(dp[0][j-1]&&dp[j][i-1]&&dp[i][n-1]) return true;
}
}
return false;
}
};class Solution {
public:
int minCut(string s) {
int n=s.size();
vector<vector<bool>> dp(n,vector<bool>(n,false));
for(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 ? dp[i+1][j-1]:true;
}
}
int ret=INT_MAX;
vector<int> dp1(n,INT_MAX);
for(int i=0;i<n;i++){
if(dp[0][i]) dp1[i]=0;
else{
for(int j=0;j<i;j++){
if(dp[j+1][i]) dp1[i]=min(dp1[j]+1,dp1[i]);
}
}
}
return dp1[n-1];//**根据状态表示返回
}
};class Solution {
public:
int longestPalindromeSubseq(string s) {
int n=s.size();
vector<vector<int>> dp(n,vector<int>(n,0));
for(int i=n-1;i>=0;i--){
dp[i][i]=1;
for(int j=i+1;j<n;j++){
if(s[i]==s[j])
dp[i][j]=dp[i+1][j-1]+2;//i+1=j时dp[i+1][j-1]=0,不变
else dp[i][j]=max(dp[i+1][j],dp[i][j-1]);
}
}
return dp[0][n-1];
}
};1312. 让字符串成为回文串的最少插入次数 - 力扣（LeetCode）
class Solution {
public:
int minInsertions(string s) {
int n=s.size();
vector<vector<int>> dp(n,vector<int>(n,0));
for(int i=n-1;i>=0;i--){
for(int j=i+1;j<n;j++){
if(s[i]==s[j]) dp[i][j]=dp[i+1][j-1];
else dp[i][j]=min(dp[i+1][j]+1,dp[i][j-1]+1);
}
}
return dp[0][n-1];
}
};class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int m=text1.size(); int n=text2.size();
vector<vector<int>> dp(m+1,vector<int>(n+1,0));
string s1=" "+text1; string s2=" "+text2;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(s1[i]==s2[j]) dp[i][j]=dp[i-1][j-1]+1;
else dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
}
}
return dp[m][n];
}
};class Solution {
public:
int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
int m=nums1.size(); int n=nums2.size();
vector<vector<int>> dp(m+1,vector<int>(n+1,0));
for(int i=1;i<m+1;i++){
for(int j=1;j<n+1;j++){
if(nums1[i-1]==nums2[j-1]) dp[i][j]=dp[i-1][j-1]+1;
else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
return dp[m][n];
}
};class Solution {
public:
int numDistinct(string s, string t) {
int ret=0;
int m=s.size(); int n=t.size();
int MOD=1e9+7;
vector<vector<double>> dp(m+1,vector<double>(n+1,0));
for(int j=0;j<=m;j++) dp[j][0]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
dp[j][i]+=dp[j-1][i];
if(s[j-1]==t[i-1]) {//**2**写成是s[j-1]==t[i-1]
// cout<<endl<<"j,i "<<j<<" "<<i<<" "<<"s[j-1]"<<s[j-1]<<" s[i-1]"<<s[i-1]<<endl;
dp[j][i]+=dp[j-1][i-1];//**1**：+=不是=。
}
// cout<<dp[j][i]<<" ";
}
// cout<<endl<<"_____________";
}
return dp[m][n];
}
};class Solution {
public:
bool isMatch(string s, string p) {
int n=s.size(); int m=p.size();
vector<vector<bool>> dp(m+1,vector<bool>(n+1,false));
s=' '+s; p=' '+p;
dp[0][0]=true;
for(int i=1;i<=m;i++){
if(p[i]=='*')
dp[i][0]=true;
else break;
}
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(p[i]=='*') dp[i][j]=dp[i-1][j]+dp[i][j-1];//**1**状态转移方程写成dp[i-1][j-1]+dp[i][j-1]
else if(p[i]=='?'||p[i]==s[j]) dp[i][j]=dp[i-1][j-1];
}
}
return dp[m][n];
}
};class Solution {
public:
bool isMatch(string s, string p) {
int m=s.size(); int n=p.size();
vector<vector<bool>> dp(m+1,vector<bool>(n+1,false));//**1**记得扩表
s=' '+s; p=' '+p;
dp[0][0]=true;
for(int i=2;i<=n;i+=2) //初始化,结合题意，匹配空串，所以i=1，3，5，7，时，且i=奇数，这个奇数之前都是可以匹配的，也就是*，所以根据*之前必须匹配有效字符串所以必须是'.'或者a~z
if(p[i]=='*') dp[0][i]=true;
else break;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(p[j]=='*') dp[i][j]=dp[i][j-2]||((p[j-1]=='.'||s[i]==p[j-1])&&dp[i-1][j]);
else dp[i][j]=(p[j]==s[i]||p[j]=='.')&&dp[i-1][j-1];
}
}
return dp[m][n];
}
};class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
int m=s1.size(); int n=s2.size();
if(m+n!=s3.size()) return false;
s1=' '+s1; s2=' '+s2; s3=' '+s3;
//优化，滚动数组
vector<bool> dp(n+1,false);
dp[0]=true;
for(int i=1;i<=n;i++){
if(s2[i]==s3[i])
dp[i]=true;
else break;
}
for(int i=1;i<=m;i++){
for(int j=0;j<=n;j++){
if(j==0){
dp[j]=s1[i]==s3[i+j]&&dp[j];
}else
dp[j]=(s1[i]==s3[i+j]&&dp[j])||(s2[j]==s3[i+j]&&dp[j-1]);
}
}
return dp[n];
//normal
// vector<vector<bool>> dp(m+1,vector<bool>(n+1,false));
// dp[0][0]=true;
// for(int i=1;i<=m;i++){
// if(s1[i]==s3[i])
// dp[i][0]=true;
// else break;
// }
// for(int j=1;j<=n;j++){
// if(s2[j]==s3[j])
// dp[0][j]=true;
// else break;
// }
// for(int i=1;i<=m;i++){
// for(int j=1;j<=n;j++){
// dp[i][j]=((s1[i]==s3[i+j])&&dp[i-1][j])||((s2[j]==s3[i+j])&&dp[i][j-1]);
// }
// }
// return dp[m][n];
}
};712. 两个字符串的最小ASCII删除和 - 力扣（LeetCode）
class Solution {
public:
int minimumDeleteSum(string s1, string s2) {
int m=s1.size(); int n=s2.size();
vector<vector<int>> dp(m+1,vector<int>(n+1,0));
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
if(s1[i-1]==s2[j-1]){
dp[i][j]=max(dp[i][j],dp[i-1][j-1]+s1[i-1]);
}
}
}
int sum=0;
for(int val:s1) sum+=val;
for(int val:s2) sum+=val;
return sum-dp[m][n]-dp[m][n];
}
};class Solution {
public:
int findLength(vector<int>& nums1, vector<int>& nums2) {
int m=nums1.size(); int n=nums2.size();
vector<vector<int>> dp(m+1,vector<int>(n+1,0));
int ret=0;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(nums1[i-1]==nums2[j-1])
dp[i][j]=dp[i-1][j-1]+1;
ret=max(ret,dp[i][j]);
}
}
return ret;
}
};