遗忘的记忆

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

思路

有 $n$ 篇分享，每篇的点赞量为 $[1, m]$ 的正整数。给定一个长度为 $n-1$ 的字符串 $s$ ，其中 $s[i]$ 为 <、= 或 >，描述第 $i$ 篇和第 $i+1$ 篇点赞量的大小关系。求满足所有约束的点赞量序列有多少种，答案对 $10^9+7$ 取模。

动态规划 + 前缀和

定义 $dp[i][j]$ 表示第 $i$ 篇分享点赞量为 $j$ 时的合法方案数。

初始状态： $dp[1][j] = 1$ ，对所有 $1 \le j \le m$ 。

转移：根据 $s[i]$ 的字符，从 $dp[i]$ 转移到 $dp[i+1]$ ：

若 $s[i] =$ <（第 $i+1$ 篇严格大于第 $i$ 篇）：

$ $dp[i+1][j] = \sum_{k=1}^{j-1} dp[i][k]$ $

即 $dp[i]$ 的前缀和，到 $j-1$ 为止。

若 $s[i] =$ >（第 $i+1$ 篇严格小于第 $i$ 篇）：

$ $dp[i+1][j] = \sum_{k=j+1}^{m} dp[i][k]$ $

即 $dp[i]$ 的后缀和，从 $j+1$ 开始。

若 $s[i] =$ =（第 $i+1$ 篇等于第 $i$ 篇）：

$ $dp[i+1][j] = dp[i][j]$ $

对于 < 和 > 的情况，前缀和与后缀和可以在遍历 $j$ 的过程中累加维护，无需额外数组，单次转移 $O(m)$ 。

最终答案为 $\sum_{j=1}^{m} dp[n][j]$ 。

样例演示

输入 $n=4, m=3, s=$ <=>：

初始： $dp = [1, 1, 1]$ （对应 $j=1,2,3$ ）
经过 <： $dp = [0, 1, 2]$ （前缀和偏移一位）
经过 =： $dp = [0, 1, 2]$ （不变）
经过 >： $dp = [3, 2, 0]$ （后缀和偏移一位）
答案 $= 3 + 2 + 0 = 5$

复杂度分析

时间复杂度： $O(n \cdot m)$ ，共 $n-1$ 次转移，每次遍历 $m$ 个值。
空间复杂度： $O(m)$ ，使用滚动数组优化，只保留当前一行。

代码

C++
Java

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

const int MOD = 1e9 + 7;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    string s;
    if(n > 1) cin >> s;

    vector<long long> dp(m + 2, 0);
    for(int j = 1; j <= m; j++) dp[j] = 1;

    for(int i = 0; i < (int)s.size(); i++){
        vector<long long> ndp(m + 2, 0);
        if(s[i] == '<'){
            long long pre = 0;
            for(int j = 1; j <= m; j++){
                ndp[j] = pre;
                pre = (pre + dp[j]) % MOD;
            }
        } else if(s[i] == '>'){
            long long suf = 0;
            for(int j = m; j >= 1; j--){
                ndp[j] = suf;
                suf = (suf + dp[j]) % MOD;
            }
        } else {
            for(int j = 1; j <= m; j++){
                ndp[j] = dp[j];
            }
        }
        dp = ndp;
    }

    long long ans = 0;
    for(int j = 1; j <= m; j++) ans = (ans + dp[j]) % MOD;
    cout << ans << endl;
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        final int MOD = 1000000007;
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        String s = "";
        if (n > 1) s = sc.next();

        long[] dp = new long[m + 2];
        for (int j = 1; j <= m; j++) dp[j] = 1;

        for (int i = 0; i < s.length(); i++) {
            long[] ndp = new long[m + 2];
            char c = s.charAt(i);
            if (c == '<') {
                long pre = 0;
                for (int j = 1; j <= m; j++) {
                    ndp[j] = pre;
                    pre = (pre + dp[j]) % MOD;
                }
            } else if (c == '>') {
                long suf = 0;
                for (int j = m; j >= 1; j--) {
                    ndp[j] = suf;
                    suf = (suf + dp[j]) % MOD;
                }
            } else {
                for (int j = 1; j <= m; j++) {
                    ndp[j] = dp[j];
                }
            }
            dp = ndp;
        }

        long ans = 0;
        for (int j = 1; j <= m; j++) ans = (ans + dp[j]) % MOD;
        System.out.println(ans);
    }
}