请问这个怎么改能够让他不Time limit exceeded
请问这个怎么改能够让他不Time limit exceeded
#include<stdio.h>
int answer(char a[], char b[], int m, int n) {
int i, j, k, number = 0;
if (n == 1) {
for (i = 0; i < m; i++) {
if (b[0] == a[i]) {
number++;
}
}
return number;
}
else if (n == 2) {
i = 0;
for (; i < m;i++)
{
if (b[0] == a[i]) {
j = i + 1;
for (; j < m; j++) {
if (b[1] == a[j]) {
number++;
}
}
}
}return number;
}
else {
i = 0;
for (; i < m; i++)
{
if (b[0] == a[i]) {
j = i + 1;
for (; j < m; j++) {
if (b[1] == a[j]) {
k = j + 1;
for (; k < m; k++) {
if (b[2] == a[k]) {
number++;
}
}
}
}
}
}return number;
}
}
int main() {
int m, n, sum = 0; char ch;
char a[100000], b[5];
scanf("%d %d", &m, &n);
scanf("%s",a);
ch=getchar();
scanf("%s", b);
sum=answer(a,b,m,n);
printf("%d\n", sum);
return 0;
}
#include<stdio.h>
int answer(char s[], char t[], int m, int n) {
if(n > m)
return 0;
int dp[n + 1][m + 1];
int len0 = m + 1;
for (int i = 0; i < len0; i++) {
dp[0][i] = 1;
}
int len = n + 1;
for (int i = 1; i < len; i++) {
dp[i][0] = 0;
}
for (int i = 1; i < len; i++) {
for (int j = 1; j < len0; j++) {
if(s[j - 1] == t[i - 1])
dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1];
else
dp[i][j] = dp[i][j - 1];
}
}
return dp[n][m];
}
int main() {
int m, n, sum = 0; char ch;
char a[100000], b[5];
scanf("%d %d", &m, &n);
scanf("%s",a);
ch=getchar();
scanf("%s", b);
sum=answer(a,b,m,n);
printf("%d\n", sum);
return 0;
}
这个用while优化一下
这种题，力扣里有很多解释
3*3*4=36