需要仔细分析，要注意base case的判断，还要注意不要漏了repaint的情况。
代码：
#include #include #include #include #include #include #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) typedef pair pii; typedef long long llong; typedef pair pll; #define mkp make_pair /*************** Program Begin **********************/ const int MOD = 1e9 + 7; long long dp[55][55]; long long C[55][55]; class BlackBoxDiv2 { public: int w, h; void calc() { C[0][0] = 1; for (int i = 1; i <= 50; i++) { C[i][0] = C[i][i] = 1; for (int j = 1; j < i; j++) { C[i][j] = C[i-1][j] + C[i-1][j-1]; C[i][j] %= MOD; } } } long long rec(int x, int y) { if (0 == x) { // base case if (0 == y) { return 1; } else { return 0; } } long long & res = dp[x][y]; if (res != -1) { return res; } res = 0; for (int s = 0; s <= y; s++) { for (int r = 0; r <= h - y; r++) { if (s + r < 1) { continue; } long long t = C[y][s] * C[h - y][r] % MOD; res += ( t * rec(x - 1, y - s) ) % MOD; res %= MOD; } } return res; } int count(string front, string side) { this->w = 0; this->h = 0; for (int i = 0; i < front.size(); i++) { w += ( front[i] == 'B' 1 : 0 ); } for (int i = 0; i < side.size(); i++) { h += ( side[i] == 'B' 1 : 0 ); } calc(); memset(dp, -1, sizeof(dp)); return rec(w, h); } }; /************** Program End ************************/