Meesho

01Distinct Moves

Given a number line with positions labeled from 0 to n, and a sequence of movements consisting of instructions 'l' (move left by 1) and 'r' (move right by 1), determine how many distinct subsequences of these moves will take you from a starting position x to an ending position y. Return the result modulo (10⁹ + 7). Notes: A subsequence is formed by deleting zero or more elements from the original sequence without changing the order of the remaining elements. A subsequence is distinct if its sequence of characters differs from another subsequence. Subsequences with identical characters from different indices are considered the same and counted only once, e.g., the subsequence containing 'l' in 'rlr' is only counted once. Starting at position j, an instruction 'l' moves to position j - 1, and an instruction 'r' moves to position j + 1. Function Description Complete the function distinctMoves in the editor with the following parameter(s):

string s: the sequence of moves
int n: the upper bound of the number line
int x: the starting point
int y: the ending point Returns int: the number of distinct subsequences modulo (10⁹+7)

Constraints

1 ≤ |s| ≤ 10³
0 ≤ x,y,n ≤ 2500

解法

二维 DP：dp[i][pos] = 用 s 前 i 个字符的某个子序列结束在位置 pos 的不同子序列数。状态转移：跳过 s[i]，或者选用 s[i](从 pos∓1 转移过来，需保证位置在 [0,n] 内)。注意「distinct」意味着相同字符值的子序列只算一次，按位置而非索引去重正好契合这种 DP。时间 O(|s|·n)，空间 O(n)。

def distinctMoves(s: str, n: int, x: int, y: int) -> int:
    MOD = 10**9 + 7
    f = [0] * (n + 1)
    f[x] = 1
    for ch in s:
        g = f[:]
        if ch == 'l':
            for pos in range(n + 1):
                if pos + 1 <= n:
                    g[pos] = (g[pos] + f[pos + 1]) % MOD
        else:
            for pos in range(n + 1):
                if pos - 1 >= 0:
                    g[pos] = (g[pos] + f[pos - 1]) % MOD
        f = g
    return f[y] % MOD

class Solution {
    int distinctMoves(String s, int n, int x, int y) {
        final int MOD = 1_000_000_007;
        long[] f = new long[n + 1];
        f[x] = 1;
        for (char ch : s.toCharArray()) {
            long[] g = f.clone();
            if (ch == 'l') {
                for (int pos = 0; pos <= n; pos++) {
                    if (pos + 1 <= n) g[pos] = (g[pos] + f[pos + 1]) % MOD;
                }
            } else {
                for (int pos = 0; pos <= n; pos++) {
                    if (pos - 1 >= 0) g[pos] = (g[pos] + f[pos - 1]) % MOD;
                }
            }
            f = g;
        }
        return (int)(f[y] % MOD);
    }
}

#include <string>
#include <vector>

class Solution {
public:
    int distinctMoves(std::string s, int n, int x, int y) {
        const int MOD = 1'000'000'007;
        std::vector<long long> f(n + 1, 0);
        f[x] = 1;
        for (char ch : s) {
            std::vector<long long> g = f;
            if (ch == 'l') {
                for (int pos = 0; pos <= n; pos++) {
                    if (pos + 1 <= n) g[pos] = (g[pos] + f[pos + 1]) % MOD;
                }
            } else {
                for (int pos = 0; pos <= n; pos++) {
                    if (pos - 1 >= 0) g[pos] = (g[pos] + f[pos - 1]) % MOD;
                }
            }
            f = g;
        }
        return (int)(f[y] % MOD);
    }
};