2021-05-21 15:48

# 算法题——辉夜大小姐以下代码的复杂度是多少

``````#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define per(i, a, b) for(int i=(a-1); i>=(b); i--)
#define qrep(i, q) for(auto i : q)
#define sz(a) (int)a.size()
#define de(a) cout<<#a<<" = "<<a<<endl
#define dd(a) cout<<#a<<" = "<<a<<" "
#define lowbit(x) x&(-x)
#define all(x) x.begin(),x.end()
#define endl "\n"
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int maxn = 1005;
const int logn = (log(maxn)/log(2))+5;
const int inf = 0x3f3f3f3f;
const ld eps = 1e-9;
char a[maxn],b[maxn];
int dp[maxn][maxn];
int solve(int x = -1)
{
//std::ios::sync_with_stdio(false);
//std::cin.tie(0);
if(x != -1){
char infile[10] = "0.in";
char outfile[10] = "0.out";
infile[0] = outfile[0] = '0'+x;
freopen(infile, "r", stdin);
freopen(outfile, "w", stdout);
}
scanf("%s%s", a+1, b+1);
int n = strlen(a+1);
int m = strlen(b+1);
memset(dp, 0, sizeof dp);
rep(i, 1, n+1){
rep(j, 1, m+1){
if(a[i] == b[j]) dp[i][j] = dp[i-1][j-1]+1;
else dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
}
}
cout << dp[n][m] << endl;
if(x != -1){
fclose(stdin);
fclose(stdout);
}
return 0;
}
int main(){
//for(int i = 0;i < 10;i++) solve(i);
solve();
}``````

• 点赞
• 写回答
• 关注问题
• 收藏
• 邀请回答

#### 2条回答默认 最新

• NoLazyForMe 2021-05-21 15:50
已采纳

O(N^2)

点赞 评论
• NoLazyForMe 2021-05-21 16:01

456789

点赞 评论