萌新真诚求助，很久以前打周赛很郁闷的问题现在还没解决，求大佬帮助。
rt 每题的时间、空间限制是多少？在哪里看？还是说统一的，那么是多少呢？
另外，为什么把数组开在 class 里面和外面不一样，里面 t 了，外面过了？？？
https://leetcode.cn/problems/number-of-ways-to-separate-numbers/
这道题，比赛交了无数次这个
class Solution {
public:
const int P = 1e9 + 7;
int n, a[3505], f[3505][3505], g[3505][3505];
void inline add(int &x, int y) {
x += y;
if (x >= P) x -= P;
}
int numberOfCombinations(string s) {
n = s.size();
for (int i = 1; i <= n; i++) a[i] = s[i - 1] - '0';
a[n + 1] = 9;
for (int i = n; i; i--) {
for (int j = n; j >= i + 1; j--) {
if (a[i] == a[j]) {
g[i][j] = 1 + g[i + 1][j + 1];
}
}
}
if (a[1] == 0) return 0;
int ans = 0;
for (int i = 1; i <= n; i++) {
if (i > 1) for (int j = i + 1; j <= n; j++) {
add(f[i][j], f[i][j - 1]);
} else for (int j = 1; j <= n; j++) f[i][j] = 1;
for (int j = i; j <= n; j++) {
if (!f[i][j]) continue;
if (a[j + 1] != 0 && j + j - i + 1 <= n) {
int k = j + j - i + 1 + 1, t = g[i][j + 1];
if (t >= j - i + 1 || a[i + t] <= a[j + 1 + t]) {
k--;
}
if (k <= n) {
add(f[j + 1][k], f[i][j]);
}
}
}
}
for (int i = 1; i <= n; i++)
add(ans, f[i][n]);
return ans;
}
};
一直 t，现在结果把3500*3500开外面就过了？
int n, a[3505], f[3505][3505], g[3505][3505];
class Solution {
public:
const int P = 1e9 + 7;
void inline add(int &x, int y) {
x += y;
if (x >= P) x -= P;
}
int numberOfCombinations(string s) {
n = s.size();
for (int i = 1; i <= n; i++) a[i] = s[i - 1] - '0';
a[n + 1] = 9;
memset(f, 0, sizeof f);
memset(g, 0, sizeof g);
for (int i = n; i; i--) {
for (int j = n; j >= i + 1; j--) {
if (a[i] == a[j]) {
g[i][j] = 1 + g[i + 1][j + 1];
}
}
}
if (a[1] == 0) return 0;
int ans = 0;
for (int i = 1; i <= n; i++) {
if (i > 1) for (int j = i + 1; j <= n; j++) {
add(f[i][j], f[i][j - 1]);
} else for (int j = 1; j <= n; j++) f[i][j] = 1;
for (int j = i; j <= n; j++) {
if (!f[i][j]) continue;
if (a[j + 1] != 0 && j + j - i + 1 <= n) {
int k = j + j - i + 1 + 1, t = g[i][j + 1];
if (t >= j - i + 1 || a[i + t] <= a[j + 1 + t]) {
k--;
}
if (k <= n) {
add(f[j + 1][k], f[i][j]);
}
}
}
}
for (int i = 1; i <= n; i++)
add(ans, f[i][n]);
return ans;
}
};
另外，运行原理是什么哦，开在外面就需要，每次清零，很阴间？？