需要用到概率论中求期望的数学公式：若 随机变量 X = X1 + X2 + ... + Xn，则 E(X) = E(X1) + E(X2) + ... + E(Xn)。
代码：
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define CHECKTIME() printf(%.2lf , (double)clock() / CLOCKS_PER_SEC) /*************** Program Begin **********************/ double dp[5001][5001]; class PalindromicSubstringsDiv1 { public: double expectedPalindromes(vector S1, vector S2) { double res = 0; memset(dp, 0, sizeof(dp)); string S; for (int i = 0; i < S1.size(); i++) { S += S1[i]; } for (int i = 0; i < S2.size(); i++) { S += S2[i]; } int N = S.size(); for (int i = 0; i < N; i++) { dp[i][i] = 1.0; res += 1.0; } for (int len = 2; len <= N; len++) { for (int i = 0; i <= N - len; i++) { int marks = 0; if (S[i] == ' ') { ++marks; } if (S[i + len - 1] == ' ') { ++marks; } if (2 == len) { if (0 == marks && S[i] == S[i + len - 1]) { dp[i][i + len - 1] = 1.0; } else if (0 != marks) { dp[i][i + len - 1] = 1.0 / 26.0; } } else { if (0 == marks && S[i] == S[i + len - 1]) { dp[i][i + len - 1] = dp[i+1][i + len - 2]; } else if (0 != marks) { dp[i][i + len - 1] = (1.0 / 26.0) * dp[i+1][i + len - 2]; } } res += dp[i][i + len - 1]; } } return res; } }; /************** Program End ************************/