题解 | #渝#_牛客博客

题目链接

题目描述

给定一个由数字 $0$ 和 $1$ 组成的三角形，一共有 $n$ 行，第 $i$ 行有 $i$ 个数字。我们使用 $A_{ij}$ 表示第 $i$ 行第 $j$ 列的数字。

从顶点 $(1, 1)$ 出发，每次可以移动到左下方 $(i+1, j)$ 或右下方 $(i+1, j+1)$ ，直到到达第 $n$ 行。这样形成一条长度为 $n$ 的路径，路径经过的数字拼接成一个字符串。

请求出有多少条路径，其对应的字符串是回文串。答案需要对 $10^9 + 7$ 取模。

解题思路

本题要求我们统计满足回文条件的路径数量。回文串的性质是 s[i] == s[n-i+1]，这意味着路径上第 $i$ 行的数字必须与第 $n-i+1$ 行的数字相同。这个首尾对应的要求，是使用“双端动态规划”或“相遇 DP”（Meet-in-the-middle DP）的典型特征。

1. 核心思想

我们可以想象有两条路径同时“生长”：一条从顶端 $(1,1)$ 向下，另一条从底端（第 $n$ 行）向上。当它们在中间相遇时，如果满足所有回文条件，就构成了一条合法的路径。

更具体地说，我们同步处理第 $i$ 行和第 $n-i+1$ 行。我们定义一个 DP 状态来记录满足回文条件的、“上半部分”和“下半部分”路径片段的数量。

2. 状态定义

我们定义 $dp[i][c_1][c_2]$ 为：

上半部分路径从 $(1,1)$ 走了 $i$ 步到达第 $i$ 行的第 $c_1$ 列。
下半部分路径（反向）从第 $n$ 行的某个位置出发，走了 $i$ 步到达第 $n-i+1$ 行的第 $c_2$ 列。
并且，对于所有 $1 \le k \le i$ ，都满足上半部分路径在第 $k$ 行的数字等于下半部分路径在第 $n-k+1$ 行的数字。
$dp[i][c_1][c_2]$ 的值就是满足上述所有条件的路径片段对的数量。

3. 状态转移

我们从 $i=1$ 开始，逐步计算到 $i = \lfloor n/2 \rfloor$ 。要计算 $dp[i][c_1][c_2]$ ，我们需要考虑 $dp[i-1][c_{1p}][c_{2p}]$ 的状态。

回文条件: 首先，必须满足当前层的回文条件，即 $A_{i, c_1} == A_{n-i+1, c_2}$ 。如果不满足，则 $dp[i][c_1][c_2] = 0$ 。
路径转移:
- 上半部分路径要到达 $(i, c_1)$ ，它必须从 $(i-1, c_1)$ 或 $(i-1, c_1-1)$ 走来。所以 $c_{1p}$ 可以是 $c_1$ 或 $c_1-1$ 。
- 下半部分路径（反向）要到达 $(n-i+1, c_2)$ ，它必须从 $(n-i+2, c_2)$ 或 $(n-i+2, c_2+1)$ 走来。所以 $c_{2p}$ 可以是 $c_2$ 或 $c_2+1$ 。

综合起来，状态转移方程为：

$dp[i][c_1][c_2] = \sum_{c_{1p} \in \{c_1, c_1-1\}} \sum_{c_{2p} \in \{c_2, c_2+1\}} dp[i-1][c_{1p}][c_{2p}]$

（所有计算需在边界范围内并对 $10^9+7$ 取模）

4. 初始状态

$i=1$ : 上半部分在 $(1,1)$ ，下半部分在 $(n, c_2)$ 。

$dp[1][1][c_2] = 1$ 如果 $A_{1,1} == A_{n,c_2}$

$dp[1][1][c_2] = 0$ 如果 $A_{1,1} \ne A_{n,c_2}$

对于所有 $1 \le c_2 \le n$ 。

5. 最终答案

计算进行到 $H = \lfloor n/2 \rfloor$ 步后，我们需要根据 $n$ 的奇偶性来合并路径。

如果 $n$ 是偶数 (n = 2H):

上半部分路径到达第 $H$ 行，下半部分路径到达第 $H+1$ 行。为了连接成一条完整路径，上半路径在 $(H, c_1)$ 的下一步必须是下半路径的起点 $(H+1, c_2)$ 。

这要求 $c_2 = c_1$ 或 $c_2 = c_1+1$ 。

总方案数 = $\sum_{c_1=1}^{H} (dp[H][c_1][c_1] + dp[H][c_1][c_1+1])$ 。
如果 $n$ 是奇数 (n = 2H+1):

上半部分路径到达第 $H$ 行，下半部分路径到达第 $H+2$ 行。它们需要通过中间的第 $H+1$ 行连接。路径形如: $(H, c_1) \to (H+1, c_{mid}) \to (H+2, c_2)$ 。

对于一个已知的 $(c_1, c_2)$ 对，连接方式有：
- 如果 $c_2 = c_1$ 或 $c_2 = c_1+2$ ：只有 1 种连接方式。
- 如果 $c_2 = c_1+1$ ：有 2 种连接方式（经过 $(H+1, c_1)$ 或 $(H+1, c_1+1)$ ）。
- 其他情况：0 种。
总方案数 = $\sum_{c_1, c_2} dp[H][c_1][c_2] \times (\text{连接数})$ 。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

const int MOD = 1e9 + 7;

int main() {
    int n;
    cin >> n;

    vector<vector<int>> a(n + 1, vector<int>(n + 1));
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= i; ++j) {
            cin >> a[i][j];
        }
    }

    if (n == 1) {
        cout << 1 << endl;
        return 0;
    }

    vector<vector<long long>> dp(n + 2, vector<long long>(n + 2, 0));

    // Base case: i = 1
    for (int c2 = 1; c2 <= n; ++c2) {
        if (a[1][1] == a[n][c2]) {
            dp[1][c2] = 1;
        }
    }

    int half = n / 2;
    for (int i = 2; i <= half; ++i) {
        vector<vector<long long>> next_dp(n + 2, vector<long long>(n + 2, 0));
        for (int c1 = 1; c1 <= i; ++c1) {
            for (int c2 = 1; c2 <= n - i + 1; ++c2) {
                if (a[i][c1] == a[n - i + 1][c2]) {
                    long long count = 0;
                    // From (i-1, c1-1)
                    count = (count + dp[c1 - 1][c2]) % MOD;
                    count = (count + dp[c1 - 1][c2 + 1]) % MOD;
                    // From (i-1, c1)
                    count = (count + dp[c1][c2]) % MOD;
                    count = (count + dp[c1][c2 + 1]) % MOD;
                    next_dp[c1][c2] = count;
                }
            }
        }
        dp = next_dp;
    }

    long long ans = 0;
    if (n % 2 == 0) { // n is even
        for (int c1 = 1; c1 <= half; ++c1) {
            ans = (ans + dp[c1][c1]) % MOD;
            ans = (ans + dp[c1][c1 + 1]) % MOD;
        }
    } else { // n is odd
        vector<vector<long long>> next_dp(n + 2, vector<long long>(n + 2, 0));
        int mid_row = half + 1;
        for (int c1 = 1; c1 <= mid_row; ++c1) {
            for (int c2 = 1; c2 <= n - mid_row + 1; ++c2) {
                 if (a[mid_row][c1] == a[n - mid_row + 1][c2]) { // This check is actually not needed for odd n
                    long long count = 0;
                    count = (count + dp[c1 - 1][c2]) % MOD;
                    count = (count + dp[c1 - 1][c2 + 1]) % MOD;
                    count = (count + dp[c1][c2]) % MOD;
                    count = (count + dp[c1][c2 + 1]) % MOD;
                    if (c1 == c2) {
                       ans = (ans + count) % MOD;
                    }
                }
            }
        }
    }
    cout << ans << endl;

    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] a = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                a[i][j] = sc.nextInt();
            }
        }

        if (n == 1) {
            System.out.println(1);
            return;
        }

        long[][] dp = new long[n + 2][n + 2];
        final int MOD = 1_000_000_007;

        // Base case: i = 1
        for (int c2 = 1; c2 <= n; c2++) {
            if (a[1][1] == a[n][c2]) {
                dp[1][c2] = 1;
            }
        }

        int half = n / 2;
        for (int i = 2; i <= half; i++) {
            long[][] nextDp = new long[n + 2][n + 2];
            for (int c1 = 1; c1 <= i; c1++) {
                for (int c2 = 1; c2 <= n - i + 1; c2++) {
                    if (a[i][c1] == a[n - i + 1][c2]) {
                        long count = 0;
                        count = (count + dp[c1 - 1][c2]) % MOD;
                        count = (count + dp[c1 - 1][c2 + 1]) % MOD;
                        count = (count + dp[c1][c2]) % MOD;
                        count = (count + dp[c1][c2 + 1]) % MOD;
                        nextDp[c1][c2] = count;
                    }
                }
            }
            dp = nextDp;
        }

        long ans = 0;
        if (n % 2 == 0) { // n is even
            for (int c1 = 1; c1 <= half; c1++) {
                ans = (ans + dp[c1][c1]) % MOD;
                ans = (ans + dp[c1][c1 + 1]) % MOD;
            }
        } else { // n is odd
            int midRow = half + 1;
            for (int c1 = 1; c1 <= half; c1++) {
                 for (int c2 = 1; c2 <= n - half + 1; c2++) {
                    if (dp[c1][c2] > 0) {
                        // Connect through middle row
                        // (half, c1) -> (midRow, c_mid) -> (midRow + 1, c2)
                        // Connections via (midRow, c1)
                        if (c2 == c1 || c2 == c1 + 1) {
                             ans = (ans + dp[c1][c2]) % MOD;
                        }
                        // Connections via (midRow, c1 + 1)
                        if (c2 == c1 + 1 || c2 == c1 + 2) {
                             ans = (ans + dp[c1][c2]) % MOD;
                        }
                    }
                 }
            }
        }
        System.out.println(ans);
    }
}

import sys

def solve():
    n = int(sys.stdin.readline())
    a = [[0] * (n + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        row = list(map(int, sys.stdin.readline().split()))
        for j in range(1, i + 1):
            a[i][j] = row[j - 1]

    if n == 1:
        print(1)
        return

    MOD = 10**9 + 7
    
    # dp[c1][c2]
    dp = [[0] * (n + 2) for _ in range(n + 2)]

    # Base case: i = 1
    for c2 in range(1, n + 1):
        if a[1][1] == a[n][c2]:
            dp[1][c2] = 1

    half = n // 2
    for i in range(2, half + 1):
        next_dp = [[0] * (n + 2) for _ in range(n + 2)]
        for c1 in range(1, i + 1):
            for c2 in range(1, n - i + 2):
                if a[i][c1] == a[n - i + 1][c2]:
                    count = 0
                    count = (count + dp[c1 - 1][c2]) % MOD
                    count = (count + dp[c1 - 1][c2 + 1]) % MOD
                    count = (count + dp[c1][c2]) % MOD
                    count = (count + dp[c1][c2 + 1]) % MOD
                    next_dp[c1][c2] = count
        dp = next_dp

    ans = 0
    if n % 2 == 0:  # n is even
        for c1 in range(1, half + 1):
            ans = (ans + dp[c1][c1]) % MOD
            ans = (ans + dp[c1][c1 + 1]) % MOD
    else:  # n is odd
        for c1 in range(1, half + 1):
            for c2 in range(1, n - half + 2):
                if dp[c1][c2] > 0:
                    # Connections
                    if c2 == c1 or c2 == c1 + 2:
                        ans = (ans + dp[c1][c2]) % MOD
                    elif c2 == c1 + 1:
                        ans = (ans + dp[c1][c2] * 2) % MOD
    
    print(ans)

solve()

算法及复杂度

算法: 双端动态规划 (Meet-in-the-middle DP)
时间复杂度: 我们需要迭代 $O(N)$ 层。在每一层，我们需要填充一个 $O(N \times N)$ 的 DP 表，每个状态的计算是常数时间。因此，总时间复杂度为 $O(N^3)$ 。
空间复杂度: 我们需要存储 DP 表。通过使用滚动数组（用一个 next_dp 数组来计算当前层），我们可以将空间复杂度优化到 $O(N^2)$ 。