难度:
Hard
题意:
思路:
代码:
class Solution {
private static int[][] c;
private static int MOD = 1000000007;
private static int[][] cache = new int[202][202];
private void init() {
c = new int[202][202];
c[0][0] = 1;
for (int i = 1;i <= 201;i++) {
c[i][0] = 1;
for (int j = 1;j < i;j++) {
c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
if (c[i][j] >= MOD) {
c[i][j] -= MOD;
}
}
c[i][i] = 1;
}
}
public int find(String S, int left, int right) {
int ret = 0;
if (right - left == 0) {
return 1;
}
if (cache[left][right] != -1) {
return cache[left][right];
}
if (S.charAt(left) == 'D') {
ret += find(S, left + 1, right);
if (ret >= MOD) {
ret -= MOD;
}
}
if (S.charAt(right - 1) == 'I') {
ret += find(S, left, right - 1);
if (ret >= MOD) {
ret -= MOD;
}
}
for (int i = left + 1;i < right;i++) {
if (S.charAt(i) == 'D' && S.charAt(i - 1) == 'I') {
ret += ((long) find(S, left, i - 1) * find(S, i + 1, right) % MOD) * c[right - left][i - left] % MOD;
if (ret >= MOD) {
ret -= MOD;
}
}
}
if (ret == 0) {
return cache[left][right] = 1;
}
return cache[left][right] = ret;
}
public int numPermsDISequence(String S) {
init();
for (int i = 0;i < 202;i++) {
for (int j = 0;j < 202;j++) {
cache[i][j] = -1;
}
}
int ret = find(S, 0, S.length());
return ret;
}
}