题解 | #遗忘的记忆#

题目链接

遗忘的记忆

题目描述

小苯是“小红书app”的一位博主，他在自己的账号中发布了 $n$ 篇分享，编号从 $1$ 到 $n$ 。

有一天他想试试看自己能不能准确的记住这 $n$ 篇分享的点赞数，但他很快就发现凭自己的记忆力根本没法准确地记住每一篇的点赞数。但他记得如下两种信息：

每篇分享的点赞量都为正数，且不超过 $m$ 。
第 $i$ 篇分享的点赞量和第 $i-1$ 篇分享的点赞量的大小关系。

他想知道，在已知这些信息的前提下，所有分享的点赞量有多少种不同的可能。

（结果可能很大，请输出其对 $1000000007$ 取模的值）

输入描述：

第一行两个正整数 $n, m$ ( $1 \le n, m \le 2000$ )，分别表示分享的总个数和每篇分享的点赞数的上限。

第二行一个长度为 $n-1$ 的字符串 $s$ ，其中只包含 >，<，= 这三种字符。如果 $s$ 的第 $i$ 个字符 (0-indexed) 是 >，则第 $i+1$ 篇分享的点赞量严格高于第 $i+2$ 篇，< 和 = 同理。

思路分析

这是一道典型的计数类动态规划问题。由于数据范围 $N, M \le 2000$ ，一个时间复杂度为 $O(N \cdot M)$ 的解法是可行的。

1. DP 状态定义

我们定义 $dp[i][j]$ 为：考虑了前 $i$ 篇分享，且第 $i$ 篇分享的点赞数为 $j$ 时的合法方案数。

我们的最终目标是求出所有 $n$ 篇分享的合法方案总数，即 $\sum_{j=1}^{m} dp[n][j]$ 。

2. 状态转移

为了计算 $dp[i][j]$ ，我们需要根据第 $i-1$ 篇和第 $i$ 篇分享之间的关系（由字符串 $s$ 的第 $i-2$ 个字符给出），从 $dp[i-1]$ 的各个状态转移而来。

基础状态：

对于第 1 篇分享 ( $i=1$ )，它可以取 $[1, m]$ 中的任何一个值，每种取法都只有 1 种方案。

所以， $dp[1][j] = 1$ ，对于所有的 $j \in [1, m]$ 。
递推关系 (对于 $i > 1$ )：

令 $s_{i-2}$ 为连接第 $i-1$ 篇和第 $i$ 篇分享的关系符号。
- 如果 $s_{i-2} = '='$ :
  
  这意味着第 $i-1$ 篇的点赞数必须等于第 $i$ 篇的点赞数。如果第 $i$ 篇点赞数为 $j$ ，那么第 $i-1$ 篇的点赞数也必须为 $j$ 。
  
  $dp[i][j] = dp[i-1][j]$
- 如果 $s_{i-2} = '<'$ :
  
  这意味着第 $i-1$ 篇的点赞数必须小于第 $i$ 篇的点赞数。如果第 $i$ 篇点赞数为 $j$ ，那么第 $i-1$ 篇的点赞数可以是 $1, 2, \dots, j-1$ 中的任意一个。
  
  $dp[i][j] = \sum_{k=1}^{j-1} dp[i-1][k]$
- 如果 $s_{i-2} = '>'$ :
  
  这意味着第 $i-1$ 篇的点赞数必须大于第 $i$ 篇的点赞数。如果第 $i$ 篇点赞数为 $j$ ，那么第 $i-1$ 篇的点赞数可以是 $j+1, j+2, \dots, m$ 中的任意一个。
  
  $dp[i][j] = \sum_{k=j+1}^{m} dp[i-1][k]$

3. 使用前缀和优化

直接按照上述转移方程计算，时间复杂度为 $O(N \cdot M^2)$ ，会超时。我们可以观察到，转移过程中频繁出现了对 $dp[i-1]$ 数组的区间求和。这种操作可以使用前缀和来进行优化。

我们定义一个前缀和数组 $prefix_sum[i-1][k] = \sum_{l=1}^{k} dp[i-1][l] \pmod{MOD}$ 。这个数组可以在计算完第 $i-1$ 行的所有 $dp$ 值后， $O(M)$ 的时间内计算出来。

这样，转移方程就可以被优化为 $O(1)$ 的查询：

对于 $s_{i-2} = '<'$ :

$dp[i][j] = \text{prefix_sum}[i-1][j-1]$
对于 $s_{i-2} = '>'$ :

$\sum_{k=j+1}^{m} dp[i-1][k]$ 可以通过总和减去前面部分得到：

$dp[i][j] = (\text{prefix_sum}[i-1][m] - \text{prefix_sum}[i-1][j] + MOD) \pmod{MOD}$

通过这种方式，我们可以在 $O(M)$ 的时间内完成从第 $i-1$ 行到第 $i$ 行的计算。总的时间复杂度就降到了 $O(N \cdot M)$ 。

4. 空间优化

在计算 $dp[i]$ 的值时，我们只依赖于 $dp[i-1]$ 的信息。因此，没有必要存储整个 $N \times M$ 的二维数组。我们可以使用两个一维数组（一个存当前行，一个存上一行）或者一个一维数组（滚动数组）来将空间复杂度从 $O(N \cdot M)$ 优化到 $O(M)$ 。

代码

cpp
java
python

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

using namespace std;
using ll = long long;

const int MOD = 1e9 + 7;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;

    vector<ll> dp(m + 1, 0);

    // 初始化 i = 1 的情况
    for (int j = 1; j <= m; ++j) {
        dp[j] = 1;
    }

    for (int i = 2; i <= n; ++i) {
        vector<ll> prefix_sum(m + 1, 0);
        for (int j = 1; j <= m; ++j) {
            prefix_sum[j] = (prefix_sum[j - 1] + dp[j]) % MOD;
        }

        vector<ll> new_dp(m + 1, 0);
        char op = s[i - 2];

        if (op == '=') {
            for (int j = 1; j <= m; ++j) {
                new_dp[j] = dp[j];
            }
        } else if (op == '<') {
            for (int j = 1; j <= m; ++j) {
                new_dp[j] = prefix_sum[j - 1];
            }
        } else { // op == '>'
            for (int j = 1; j <= m; ++j) {
                new_dp[j] = (prefix_sum[m] - prefix_sum[j] + MOD) % MOD;
            }
        }
        dp = new_dp;
    }

    ll total_sum = 0;
    for (int j = 1; j <= m; ++j) {
        total_sum = (total_sum + dp[j]) % MOD;
    }

    cout << total_sum << 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 m = sc.nextInt();
        String s = sc.next();
        
        final int MOD = 1_000_000_007;

        long[] dp = new long[m + 1];

        // 初始化 i = 1
        for (int j = 1; j <= m; j++) {
            dp[j] = 1;
        }

        for (int i = 2; i <= n; i++) {
            long[] prefixSum = new long[m + 1];
            for (int j = 1; j <= m; j++) {
                prefixSum[j] = (prefixSum[j - 1] + dp[j]) % MOD;
            }

            long[] newDp = new long[m + 1];
            char op = s.charAt(i - 2);

            if (op == '=') {
                for (int j = 1; j <= m; j++) {
                    newDp[j] = dp[j];
                }
            } else if (op == '<') {
                for (int j = 1; j <= m; j++) {
                    newDp[j] = prefixSum[j - 1];
                }
            } else { // op == '>'
                for (int j = 1; j <= m; j++) {
                    newDp[j] = (prefixSum[m] - prefixSum[j] + MOD) % MOD;
                }
            }
            dp = newDp;
        }

        long totalSum = 0;
        for (int j = 1; j <= m; j++) {
            totalSum = (totalSum + dp[j]) % MOD;
        }

        System.out.println(totalSum);
    }
}

import sys

def solve():
    try:
        n, m = map(int, sys.stdin.readline().split())
        s = sys.stdin.readline().strip()
    except (IOError, ValueError):
        return

    MOD = 10**9 + 7

    # dp[j] 表示当前处理到第 i 篇，且点赞数为 j 的方案数
    dp = [0] * (m + 1)

    # 初始化 i = 1 的情况
    for j in range(1, m + 1):
        dp[j] = 1

    for i in range(2, n + 1):
        prefix_sum = [0] * (m + 1)
        for j in range(1, m + 1):
            prefix_sum[j] = (prefix_sum[j - 1] + dp[j]) % MOD

        new_dp = [0] * (m + 1)
        op = s[i - 2]

        if op == '=':
            for j in range(1, m + 1):
                new_dp[j] = dp[j]
        elif op == '<':
            for j in range(1, m + 1):
                new_dp[j] = prefix_sum[j - 1]
        else:  # op == '>'
            for j in range(1, m + 1):
                new_dp[j] = (prefix_sum[m] - prefix_sum[j] + MOD) % MOD
        
        dp = new_dp

    total_sum = sum(dp) % MOD
    print(total_sum)

solve()

算法及复杂度

算法：动态规划 + 前缀和优化
时间复杂度： $O(N \cdot M)$ 。我们有一个两层的循环，外层循环 $N$ 次，内层循环 $M$ 次来构建前缀和数组和新的 DP 数组。
空间复杂度： $O(M)$ 。通过使用滚动数组（或在每次迭代中创建新数组）的方式，我们只需要存储上一行和当前行的 DP 状态，以及一个前缀和数组，空间都与 $M$ 成正比。