牛客REAL645题解：动态规划求解朋友聚会问题（三维DP+状态转移优化）
一、题目解读
牛客REAL645题要求解决一个朋友聚会安排问题：用户需每天邀请不同朋友（A/B/C）聚会，总天数为n，求所有可能的安排方案数。题目核心在于组合数学与状态约束——每日选择不能与前一天重复，且总天数n可变。需设计高效算法避免指数级计算。
二、解题思路
采用动态规划（DP），核心思想是将大问题分解为子问题，利用已计算状态避免重复计算。
1. 状态定义：创建三维数组dp[a][b][c][last]，表示使用a次A、b次B、c次C，且最后一天选择朋友last（0=A,1=B,2=C）时的方案数。
2. 状态转移方程：根据“当前天不能与前一天选同人”的规则，递推公式如：若最后一天选A（last=0），则前一天需选B或C，方案数累加对应子状态。
3. 边界处理：初始化第一天可选任意朋友，总天数需≥2天（单日无解），避免无效状态计算。
三、解题步骤
1. 初始化：
○ dp[1][0][0][0]=1（第一天选A），dp[0][1][0][1]=1（选B），dp[0][0][1][2]=1（选C），覆盖所有起始状态。
2. 三重循环遍历所有可能次数组合：
○ 当a+b+c<2（总天数不足2天）跳过，因题目要求至少2天聚会。
3. 状态转移分支：
○ 若last=0且a>0，则前一天可选B或C，累加对应方案数：dp[a][b][c][0] += dp[a-1][b][c][1] + dp[a-1][b][c][2]（MOD防溢出）。
○ 同理处理last=1(B)、last=2(C)的情况，确保不重复。
4. 结果汇总：最终方案数为三种末尾状态的总和，取模输出。
四、代码及注释
#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; // 选A
dp[0][1][0][1] = 1; // 选B
dp[0][0][1][2] = 1; // 选C
for (int a = 0; a <= n; ++a) { // 遍历A次数
for (int b = 0; b <= n; ++b) { // B次数
for (int c = 0; c <= n; ++c) { // C次数
if (a + b + c < 2) continue; // 总天数至少2天
for (int last = 0; last < 3; ++last) { // 末尾状态（A/B/C）
if (last == 0 && a == 0) continue; // 若选A但A次数为0，跳过
if (last == 1 && b == 0) continue; // 同理B
if (last == 2 && c == 0) continue; // 同理C
int& val = dp[a][b][c][last]; // 引用当前状态
// 前一天不能和今天选同一个人
if (last == 0 && a > 0) { // 若当前选A，前一天需选B或C
val = (val + dp[a - 1][b][c][1]) % MOD; // B的方案
val = (val + dp[a - 1][b][c][2]) % MOD; // C的方案
}
if (last == 1 && b > 0) { // 选B，前一天A或C
val = (val + dp[a][b - 1][c][0]) % MOD;
val = (val + dp[a][b - 1][c][2]) % MOD;
}
if (last == 2 && c > 0) { // 选C，前一天A或B
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;
}五、总结
1. 动态规划优势：通过状态分解将指数级问题转化为多项式复杂度（本例O(n^3)），利用边界与转移方程高效求解。
2. MOD运算必要性：题目隐含方案数可能超大，需提前设定模数避免溢出，保障结果正确性。
3. 扩展思考：此类问题可进一步优化空间（如滚动数组），或结合数学组合公式验证结果。
4. 应用场景：适用于有约束条件的多阶段决策问题，如资源分配、路径规划等。
原创内容 转载请注明出处
