---
# System prepended metadata

title: 1220. Count Vowels Permutation
tags: [Leetcode, Dynamic Programming, Hard]

---

# 1220. Count Vowels Permutation
###### tags: `Leetcode` `Hard` `Dynamic Programming`
Link: https://leetcode.com/problems/count-vowels-permutation/description/
## 思路
![](https://i.imgur.com/yy3Ma4o.png)
根据上图建造状态转移方程
## Code
```java=
class Solution {
    public int countVowelPermutation(int n) {
        long[] dp = new long[5];
        Arrays.fill(dp, 1);
        int mod = 1000000007;
        for(int i=1; i<n; i++){
            long[] temp = dp.clone();
            temp[0] = (dp[1]+dp[2]+dp[4])%mod;
            temp[1] = (dp[0]+dp[2])%mod;
            temp[2] = (dp[1]+dp[3])%mod;
            temp[3] = dp[2];
            temp[4] = (dp[2]+dp[3])%mod;
            dp = temp;
        }
        
        long ans = 0;
        for(int i=0; i<5; i++){
            ans = (ans+dp[i])%mod;
        }
        return (int)ans;
    }
}
```