牛客网REAL645题：动态规划计算小红的暑假（附完整代码解析）
一、问题重述与分析
小红有3个朋友，暑假共3n天，每天选择一位朋友游玩，要求：
每个朋友恰好被选择n次
不能连续两天选择同一位朋友
这实际上是一个受限排列组合问题，需要计算所有满足条件的序列数量。
二、动态规划解法详解
状态设计
采用四维dp数组： DP[a][b][c][last] 表示：
已选择朋友A
a次已选择朋友B
b次已选择朋友C
c次最后选择的朋友是
last（0=A,1=B,2=C）
状态转移
对于每个状态，考虑前一天的选择：
如果今天选A，那么前一天只能选B或C
如果今天选B，那么前一天只能选A或C
如果今天选C，那么前一天只能选A或B
转移方程：
dp[a][b][c][0] = dp[a-1][b][c][1] + dp[a-1][b][c][2] dp[a][b][c][1] = dp[a][b-1][c][0] + dp[a][b-1][c][2] dp[a][b][c][2] = dp[a][b][c-1][0] + dp[a][b][c-1][1]
初始化
第一天可以选择任意朋友：
dp[1][0][0][0] = 1 // 第一天选A dp[0][1][0][1] = 1 // 第一天选B dp[0][0][1][2] = 1 // 第一天选C
结果计算
最终结果是所有朋友都被选择n次的情况之和：
result = dp[n][n][n][0] + dp[n][n][n][1] + dp[n][n][n][2]
三、优化思考
实际可以压缩状态到三维，因为a+b+c等于当前总天数。但四维状态更直观易于理解，适合教学。
四、完整代码
#include <iostream>
#include <vector>
using namespace std;
const int MOD = 1e9 + 7;
int main() {
int n;
cin >> n;
// dp[a][b][c][last] 表示用了a次A，b次B，c次C，最后一个是last的方案数
// last取值0(A),1(B),2(C)
vector<vector<vector<vector<int>>>> dp(
n+1, vector<vector<vector<int>>>(
n+1, vector<vector<int>>(
n+1, vector<int>(3, 0))));
// 初始化：第一天可以选择任意朋友
dp[1][0][0][0] = 1;
dp[0][1][0][1] = 1;
dp[0][0][1][2] = 1;
for(int a = 0; a <= n; ++a) {
for(int b = 0; b <= n; ++b) {
for(int c = 0; c <= n; ++c) {
if(a + b + c < 2) continue; // 总天数至少2天
for(int last = 0; last < 3; ++last) {
if(last == 0 && a == 0) continue;
if(last == 1 && b == 0) continue;
if(last == 2 && c == 0) continue;
int &val = dp[a][b][c][last];
// 前一天不能和今天选同一个人
if(last == 0 && a > 0) {
val = (val + dp[a-1][b][c][1]) % MOD;
val = (val + dp[a-1][b][c][2]) % MOD;
}
if(last == 1 && b > 0) {
val = (val + dp[a][b-1][c][0]) % MOD;
val = (val + dp[a][b-1][c][2]) % MOD;
}
if(last == 2 && c > 0) {
val = (val + dp[a][b][c-1][0]) % MOD;
val = (val + dp[a][b][c-1][1]) % MOD;
}
}
}
}
}
// 最终结果是三种最后选择情况的加和
int res = 0;
for(int last = 0; last < 3; ++last) {
res = (res + dp[n][n][n][last]) % MOD;
}
cout << res << endl;
return 0;
}扩展思考
如果朋友数量变为4个，算法该如何调整？欢迎在评论区讨论你的想法！
原创内容 转载请注明出处
