DI 序列的有效排列

/*
 * Problem: Given a string 's' of length n where 's[i]' is:
 * - 'D' means decreasing
 * - 'I' means increasing
 * A valid permutation is a permutation of numbers [0, 1, ..., n] that satisfies:
 * - If s[i] == 'D', then perm[i] > perm[i+1]
 * - If s[i] == 'I', then perm[i] < perm[i+1]
 * Return the number of such valid permutations modulo 10^9 + 7.
 */

import java.util.stream.IntStream;
import java.util.stream.Stream;

public class ValidPermutationsStream {
    private static final int MOD = 1000000007;

    public int numPermsDISequence(String s) {
        int n = s.length();
        int[][] dp = new int[n + 1][n + 1];
        IntStream.range(0, n + 1).forEach(i -> dp[0][i] = 1);

        IntStream.range(1, n + 1).forEach(i -> {
            if (s.charAt(i - 1) == 'D') {
                for (int j = i - 1; j >= 0; j--) {
                    dp[i][j] = (dp[i][j + 1] + dp[i - 1][j]) % MOD;
                }
            } else {
                for (int j = 0; j < i; j++) {
                    dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % MOD;
                }
            }
        });

        return dp[n][0];
    }

    public static void main(String[] args) {
        ValidPermutationsStream vp = new ValidPermutationsStream();
        System.out.println(vp.numPermsDISequence("DID")); // Output: 5
        System.out.println(vp.numPermsDISequence("D"));   // Output: 1
    }
}