小红的暑假

[题目链接](https://www.nowcoder.com/practice/6770931d7bb74c29863c23c375907c33)

思路

小红和三位朋友共有 $3n$ 天暑假，每天选一位朋友玩，最终每位朋友恰好玩了 $n$ 天。要求不存在连续两天找同一个朋友。问满足条件的方案数，结果对 $10^9+7$ 取模。

动态规划——逐天填充

将三位朋友编号为 $0, 1, 2$ 。我们逐天决定当天和谁玩，用 DP 跟踪已经和每位朋友玩了多少天，以及昨天找的是谁。

设 $dp[i][j][last]$ 表示：已经和朋友 0 玩了 $i$ 天、和朋友 1 玩了 $j$ 天（则和朋友 2 玩了 $t - i - j$ 天，其中 $t$ 是当前总天数），且最后一天找的是朋友 $last$ 的方案数。

转移：在第 $t+1$ 天，可以选择任意一位不等于 $last$ 的朋友 $c$ ，前提是该朋友的已玩天数尚未达到 $n$ ：

选朋友 0（ $last \neq 0$ 且 $i + 1 \leq n$ ）： $\text{ndp}[i+1][j][0] \mathrel{+}= dp[i][j][1] + dp[i][j][2]$
选朋友 1（ $last \neq 1$ 且 $j + 1 \leq n$ ）： $\text{ndp}[i][j+1][1] \mathrel{+}= dp[i][j][0] + dp[i][j][2]$
选朋友 2（ $last \neq 2$ 且 $k + 1 \leq n$ ，其中 $k = t - i - j$ ）： $\text{ndp}[i][j][2] \mathrel{+}= dp[i][j][0] + dp[i][j][1]$

初始状态：第 1 天可以选择任意朋友，即 $dp[1][0][0] = dp[0][1][1] = dp[0][0][2] = 1$ 。

答案： $dp[n][n][0] + dp[n][n][1] + dp[n][n][2]$ 。

优化遍历范围

对于第 $t$ 天的状态 $(i, j)$ ，需满足 $0 \leq i \leq n$ 、 $0 \leq j \leq n$ 、 $0 \leq t - i - j \leq n$ ，即 $j \geq t - i - n$ 且 $j \leq t - i$ 。通过精确计算循环上下界，只遍历有效状态，避免无效访问。使用滚动数组（交换 dp 和 ndp）节省空间。

复杂度分析

时间复杂度： $O(n^3)$ 。总共 $3n$ 步，每步遍历的有效 $(i, j)$ 对数量在中间步骤最多为 $O(n^2)$ ，总计 $O(n^3)$ 。
空间复杂度： $O(n^2)$ ，两个 $n \times n \times 3$ 的数组。

代码

C++
Java

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;
const int MAXN = 1002;

long long A[MAXN][MAXN][3], B[MAXN][MAXN][3];

int main() {
    int n;
    scanf("%d", &n);
    if (n == 0) { puts("1"); return 0; }

    auto dp = A, ndp = B;
    dp[1][0][0] = dp[0][1][1] = dp[0][0][2] = 1;

    for (int t = 2; t <= 3 * n; t++) {
        int imin = max(0, t - 2 * n), imax = min(n, t);
        for (int i = imin; i <= imax; i++) {
            int jl = max(0, t - i - n), jr = min(n, t - i);
            for (int j = jl; j <= jr; j++)
                ndp[i][j][0] = ndp[i][j][1] = ndp[i][j][2] = 0;
        }
        int pi0 = max(0, t - 1 - 2 * n), pi1 = min(n, t - 1);
        for (int i = pi0; i <= pi1; i++) {
            int pj0 = max(0, t - 1 - i - n), pj1 = min(n, t - 1 - i);
            for (int j = pj0; j <= pj1; j++) {
                int k = t - 1 - i - j;
                long long v0 = dp[i][j][0], v1 = dp[i][j][1], v2 = dp[i][j][2];
                if ((v0 | v1 | v2) == 0) continue;
                if (i + 1 <= n) ndp[i+1][j][0] = (ndp[i+1][j][0] + v1 + v2) % MOD;
                if (j + 1 <= n) ndp[i][j+1][1] = (ndp[i][j+1][1] + v0 + v2) % MOD;
                if (k + 1 <= n) ndp[i][j][2] = (ndp[i][j][2] + v0 + v1) % MOD;
            }
        }
        swap(dp, ndp);
    }
    printf("%lld\n", (dp[n][n][0] + dp[n][n][1] + dp[n][n][2]) % MOD);
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        final int MOD = 1_000_000_007;
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        if (n == 0) { System.out.println(1); return; }

        int m = n + 2;
        long[][][] dp = new long[m][m][3], ndp = new long[m][m][3];
        dp[1][0][0] = dp[0][1][1] = dp[0][0][2] = 1;

        for (int t = 2; t <= 3 * n; t++) {
            int imin = Math.max(0, t - 2 * n), imax = Math.min(n, t);
            for (int i = imin; i <= imax; i++) {
                int jl = Math.max(0, t - i - n), jr = Math.min(n, t - i);
                for (int j = jl; j <= jr; j++)
                    ndp[i][j][0] = ndp[i][j][1] = ndp[i][j][2] = 0;
            }
            int pi0 = Math.max(0, t - 1 - 2 * n), pi1 = Math.min(n, t - 1);
            for (int i = pi0; i <= pi1; i++) {
                int pj0 = Math.max(0, t - 1 - i - n), pj1 = Math.min(n, t - 1 - i);
                for (int j = pj0; j <= pj1; j++) {
                    int k = t - 1 - i - j;
                    long v0 = dp[i][j][0], v1 = dp[i][j][1], v2 = dp[i][j][2];
                    if ((v0 | v1 | v2) == 0) continue;
                    if (i + 1 <= n) ndp[i+1][j][0] = (ndp[i+1][j][0] + v1 + v2) % MOD;
                    if (j + 1 <= n) ndp[i][j+1][1] = (ndp[i][j+1][1] + v0 + v2) % MOD;
                    if (k + 1 <= n) ndp[i][j][2] = (ndp[i][j][2] + v0 + v1) % MOD;
                }
            }
            long[][][] tmp = dp; dp = ndp; ndp = tmp;
        }
        System.out.println((dp[n][n][0] + dp[n][n][1] + dp[n][n][2]) % MOD);
    }
}