牛客网288555题解题指南：动态规划求解小红的暑假（附代码解析）
2个月前 (06-21)
一、题目解读
牛客网288555题要求解决一个组合数学问题：有三位朋友，每天需邀请其中一位参加聚会，但不能连续两天邀请同一位朋友。给定天数n，求满足条件的不同邀请方案总数。题目考察动态规划、状态转移及组合计数，属于中等难度算法题。
二、解题思路：动态规划 + 状态压缩
核心思想是将问题分解为子问题，利用动态规划记录中间状态。定义四维DP数组：dp[a][b][c][last]，表示已邀请朋友1 a次、朋友2 b次、朋友3 c次，且最后一天邀请的是last（1/2/3）的方案数。通过状态转移方程，枚举下一位朋友的选择，避免重复计数。
三、解题步骤
1. 初始化：第一天可选任意朋友，初始化dp[1][0][0][1]、dp[0][1][0][2]、dp[0][0][1][3]为1。
2. 状态转移循环：遍历所有可能的(a,b,c)组合，若当前状态dp[a][b][c][last]有效：
枚举下一个朋友next（1/2/3），跳过与last相同的情况。
更新次数：na=a+(next=1), nb=b+(next=2), nc=c+(next=3)。
若次数不超n，累加方案数：dp[na][nb][nc][next] += dp[a][b][c][last]。
3. 结果计算：最终方案为所有朋友均被邀请n次的状态总和，即dp[n][n][n][1] + dp[n][n][n][2] + dp[n][n][n][3]（取模防止溢出）。
四、代码与注释
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int MOD = 1e9 + 7; // 取模常数，防止结果溢出
const int MAX_N = 100; // 最大天数限制
// dp[a][b][c][last] 表示选了a次朋友1，b次朋友2，c次朋友3，最后选的是last的方案数
int dp[MAX_N+1][MAX_N+1][MAX_N+1][4];
int main() {
int n;
cin >> n; // 输入天数n
memset(dp, 0, sizeof(dp)); // 初始化dp数组为0
// 初始状态：第一天可选任意朋友
dp[1][0][0][1] = 1; // 选朋友1一次，最后为1
dp[0][1][0][2] = 1; // 选朋友2一次，最后为2
dp[0][0][1][3] = 1; // 选朋友3一次，最后为3
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 == 0) continue; // 跳过全0状态（无效）
for (int last = 1; last <= 3; ++last) {
if (dp[a][b][c][last] == 0) continue; // 当前状态无效则跳过
// 尝试选择下一个朋友
for (int next = 1; next <= 3; ++next) {
if (next == last) continue; // 避免连续选同一人
int na = a, nb = b, nc = c;
if (next == 1) na++; // 更新次数
else if (next == 2) nb++;
else nC++;
if (na <= n && nb <= n && nc <= n) {
// 累加方案数（取模）
dp[na][nb][nc][next] = (dp[na][nb][nc][next] + dp[a][b][c][last]) % MOD;
}
}
}
}
}
}
// 最终结果是所有朋友都被选n次的总和
int result = 0;
for (int last = 1; last <= 3; ++last) {
result = (result + dp[n][n][n][last]) % MOD; // 取模求和
}
cout << result << endl;
return 0;
}五、总结
本题通过动态规划巧妙解决组合限制问题，关键在于四维状态设计（次数+末尾选择）和转移条件的严谨性。优化点包括利用取模运算避免大数溢出，以及跳过无效状态提升效率。掌握此类状态压缩技巧，可应对更多复杂计数问题。
原创内容 转载请注明出处
