Skip to Content
CTRL K

Empty String

Editorial

Sea dp[i][j]\texttt{dp}[i][j] el número de formas de vaciar la subcadena [i,j][i, j].

Para calcular dp[i][j]\texttt{dp}[i][j], recorremos los índices kk entre ii y jj donde s[i]=s[k]s[i] = s[k].

Luego, si elegimos eliminar s[i]s[i] y s[k]s[k], primero hay que eliminar el rango [i+1,k−1][i + 1, k - 1] (para que s[i]s[i] y s[k]s[k] queden adyacentes). Aquí, el número de formas de eliminar el rango [i+1,k−1][i + 1, k - 1] es dp[i+1][k−1]\texttt{dp}[i + 1][k - 1].

También hay que eliminar [k+1,j][k + 1, j] para que se elimine toda la subcadena [i,j][i, j] (el número de formas de hacer esto es dp[k+1][j]dp[k + 1][j]).

Como podemos eliminar la subcadena [i,k][i, k] y [k+1,j][k + 1, j] en cualquier orden, también multiplicamos esto por ((j−i+1)/2(k−i+1)/2){(j - i + 1) / 2}\choose {(k - i + 1) / 2} (nótese que dividimos los tamaños por dos porque eliminamos las letras de a pares).

Así, nuestra transición sería

dp[i][j]=∑dp[i+1][k−1]∗dp[k+1][j]∗((j−i+1)/2(k−i+1)/2) \texttt{dp}[i][j] = \sum{\texttt{dp}[i + 1][k - 1] * \texttt{dp}[k + 1][j] * {{(j - i + 1) / 2}\choose {(k - i + 1) / 2}}}

tal que s[i]=s[k]s[i] = s[k].

Implementación

Complejidad temporal: O(N3)\mathcal{O}(N^3)

#include <bits/stdc++.h>
using namespace std;
 
#define N 500
#define MOD 1000000007
 
int add(int a, int b) {
	if ((a += b) >= MOD) a -= MOD;
	return a;
}
 
int mul(int a, int b) { return int(1LL * a * b % MOD); }
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
 
	int n, i, j, k;
	static int dp[N + 1][N + 1], choose[N / 2 + 1][N / 2 + 1];
	static string s;
 
	cin >> s;
	n = (int)s.size();
 
	choose[0][0] = 1;
	for (i = 1; i <= n / 2; ++i) {
		choose[i][0] = 1;
		for (int j = 1; j <= i; ++j)
			choose[i][j] = add(choose[i - 1][j], choose[i - 1][j - 1]);
	}
 
	for (i = 0; i + 1 <= n; ++i) dp[i + 1][i] = 1;
	for (i = n - 1; i >= 0; --i)
		for (j = i + 1; j < n; j += 2) {
			for (k = i + 1; k <= j; k += 2)
				if (s[i] == s[k]) {
					int temp = mul(dp[i + 1][k - 1], dp[k + 1][j]);
					temp = mul(temp, choose[(j - i + 1) / 2][(k - i + 1) / 2]);
					dp[i][j] = add(dp[i][j], temp);
				}
		}
	cout << dp[0][n - 1] << '\n';
}
import java.io.*;
 
public class EmptyStrings {
	private static final int MOD = 1000000007;
 
	private static int add(int a, int b) {
		int sum = a + b;
		return sum >= MOD ? sum - MOD : sum;
	}
 
	private static int mul(int a, int b) { return (int)(1L * a * b % MOD); }
 
	public static void main(String[] args) throws Exception {
		char[] s = new BufferedReader(new InputStreamReader(System.in))
		               .readLine()
		               .toCharArray();
 
		final int n = s.length;
		int[][] dp = new int[n + 1][n + 1];
		int[][] choose = new int[n / 2 + 1][n / 2 + 1];
		choose[0][0] = 1;
		for (int i = 1; i <= n / 2; i++) {
			choose[i][0] = 1;
			for (int j = 1; j <= i; j++)
				choose[i][j] = add(choose[i - 1][j], choose[i - 1][j - 1]);
		}
 
		for (int i = 0; i + 1 <= n; i++) { dp[i + 1][i] = 1; }
 
		for (int i = n - 1; i >= 0; i--) {
			for (int j = i + 1; j < n; j += 2) {
				for (int k = i + 1; k <= j; k += 2)
					if (s[i] == s[k]) {
						int temp = mul(dp[i + 1][k - 1], dp[k + 1][j]);
						temp = mul(temp, choose[(j - i + 1) / 2][(k - i + 1) / 2]);
						dp[i][j] = add(dp[i][j], temp);
					}
			}
		}
 
		System.out.println(dp[0][n - 1]);
	}
}
N = 500
MOD = 10**9 + 7
 
 
def add(a: int, b: int) -> int:
	return (a + b) % MOD
 
 
def mul(a: int, b: int) -> int:
	return (a * b) % MOD
 
 
s = input()
n = len(s)
 
dp = [[0] * (N + 1) for _ in range(N + 1)]
choose = [[0] * (N // 2 + 1) for _ in range(N // 2 + 1)]
 
choose[0][0] = 1
for i in range(1, n // 2 + 1):
	choose[i][0] = 1
	for j in range(1, i + 1):
		choose[i][j] = add(choose[i - 1][j], choose[i - 1][j - 1])
 
 
for i in range(0, n):
	dp[i + 1][i] = 1
 
for i in range(n - 1, -1, -1):
	for j in range(i + 1, n, 2):
		for k in range(i + 1, j + 1, 2):
			if s[i] == s[k]:
				temp = mul(dp[i + 1][k - 1], dp[k + 1][j])
				temp = mul(temp, choose[(j - i + 1) // 2][(k - i + 1) // 2])
				dp[i][j] = add(dp[i][j], temp)
 
print(dp[0][n - 1])
Fundamentos