2020-10-20

class Solution { public int numPermsDISequence(String S) { int MOD = 1_000_000_007; int N = S.length(); // dp[i][j] : Num ways to place P_i with relative rank j int[][] dp = new int[N+1][N+1]; Arrays.fill(dp[0], 1); for (int i = 1; i <= N; ++i) { for (int j = 0; j <= i; ++j) { if (S.charAt(i-1) == 'D') { for (int k = j; k < i; ++k) { dp[i][j] += dp[i-1][k]; dp[i][j] %= MOD; } } else { for (int k = 0; k < j; ++k) { dp[i][j] += dp[i-1][k]; dp[i][j] %= MOD; } } } } int ans = 0; for (int x: dp[N]) { ans += x; ans %= MOD; } return ans; } }