首先就是暴力嘗試但是會逾時，通過54/63測試用例
public static int numDistinct1(String s, String t) {
char[] sChars = s.toCharArray();
char[] tChars = t.toCharArray();
int sLen = sChars.length;
int tLen = tChars.length;
if (tLen == 1) {
int count = 0;
for (int i = 0; i < sLen; i++) {
if (sChars[i] == tChars[0]) {
count++;
}
}
return count;
}
int count = 0;
for (int i = 0; i < sLen; i++) {
if (sChars[i] == tChars[0]) {
count += numDistinct1(s.substring(i + 1), t.substring(1));
}
}
return count;
}
再就是嘗試動态規劃,找這個狀态轉移方程花了一個多小時
public int numDistinct(String s, String t) {
char[] sChars = s.toCharArray();
char[] tChars = t.toCharArray();
int sLen = sChars.length;
int tLen = tChars.length;
int[][] dp = new int[sLen + 1][tLen + 1];
int count = 0;
for (int i = 1; i <= sLen; i++) {
if (sChars[i - 1] == tChars[0]) {
count++;
dp[i][1] = count;
} else {
dp[i][1] = dp[i - 1][1];
}
}
for (int i = 1; i <= sLen; i++) {
for (int j = 2; j <= tLen; j++) {
if (sChars[i - 1] == tChars[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
//dp[i][j]表示前i個元素中包含多少個前j個元素
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[sLen][tLen];
}