aboutsummaryrefslogtreecommitdiff
path: root/count_vowels_permutation.cpp
blob: 807a1f41457d7ae0dd30c8563639fe567d0703b0 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "leetcode.h"
class Solution {
public:
  int countVowelPermutation(int n) {
    int ans = 0;
    memo.resize(n + 1, vector<int>(5, -1));
    for (int i = 0; i < 5; i++)
      ans += dp(n, i), ans %= mod;
    return ans;
  }

private:
  int mod = 1e9 + 7;
  vector<vector<int>> relation = {{1}, {0, 2}, {0, 1, 3, 4}, {2, 4}, {0}}, memo;
  int dp(int n, int v) {
    if (n == 1)
      return 1;
    if (memo[n][v] != -1)
      return memo[n][v];
    memo[n][v] = 0;
    for (int &i : relation[v])
      memo[n][v] += dp(n - 1, i), memo[n][v] %= mod;
    return memo[n][v];
  }
};

int main() {
  Solution obj;
  cout << obj.countVowelPermutation(1);
}