1220.统计元音字母序列的数目
题目描述思路
动态规划
Python实现Java实现
1220.统计元音字母序列的数目 题目描述
统计元音字母序列的数目
思路 动态规划
根据题意给定的规则可以推断出以下规则：
元音字母’a’前面只能跟着’e’，‘i’，‘u’，后面只能跟着’e’；元音字母’e’前面只能跟着’a’，‘i’，后面只能跟着’a’，‘i’；元音字母’i’前面只能跟着’e’，‘o’，后面只能跟着’i’，‘u’；元音字母’o’前面只能跟着’i’，后面只能跟着’i’，‘u’；元音字母’u’前面只能跟着’i’，‘o’，后面只能跟着’a’。
设dp[i][j]代表当前长度为i且以字符j结尾的字符串的数目，其中此j=0,1,2,3,4分别代表’a’,‘e’,‘i’,‘o’,‘u’，通过以上的字符规则，所以有如下递推式：
d
p
[
i
]
[
0
]
=
d
p
[
i
−
1
]
[
1
]
+
d
p
[
i
−
1
]
[
2
]
+
d
p
[
i
−
1
]
[
4
]
dp[i][0] = dp[i-1][1] + dp[i-1][2] + dp[i-1][4]
dp[i][0]=dp[i−1][1]+dp[i−1][2]+dp[i−1][4]
d
p
[
i
]
[
1
]
=
d
p
[
i
−
1
]
[
0
]
+
d
p
[
i
−
1
]
[
2
]
dp[i][1] = dp[i-1][0] + dp[i-1][2]
dp[i][1]=dp[i−1][0]+dp[i−1][2]
d
p
[
i
]
[
2
]
=
d
p
[
i
−
1
]
[
1
]
+
d
p
[
i
−
1
]
[
3
]
dp[i][2] = dp[i-1][1] + dp[i-1][3]
dp[i][2]=dp[i−1][1]+dp[i−1][3]
d
p
[
i
]
[
3
]
=
d
p
[
i
−
1
]
[
2
]
dp[i][3] = dp[i-1][2]
dp[i][3]=dp[i−1][2]
d
p
[
i
]
[
4
]
=
d
p
[
i
−
1
]
[
2
]
+
d
p
[
i
−
1
]
[
3
]
dp[i][4] = dp[i-1][2] + dp[i-1][3]
dp[i][4]=dp[i−1][2]+dp[i−1][3]
所以最终答案应为 ∑ i = 0 4 d p [ n ] [ i ] sum_{i=0}^{4}dp[n][i] ∑i=04dp[n][i]模1e9+7。另外，计算过程中，只需要保留前一个状态即可推导出后一个状态，所以不需要整个dp数组都存储。
Python实现class Solution:
def countVowelPermutation(self, n: int) -> int:
dp = (1, 1, 1, 1, 1)
for i in range(n-1):
dp = ((dp[1] + dp[2] + dp[4]) % 1000000007, (dp[0] + dp[2]) % 1000000007, (dp[1] + dp[3]) % 1000000007, (dp[2]) % 1000000007, (dp[2] + dp[3]) % 1000000007)
return sum(dp) % 1000000007
Java实现
class Solution {
public int countVowelPermutation(int n) {
long mod = 1000000007;
long[] dp = new long[5];
long[] ndp = new long[5];
for (int i = 0; i < 5; ++i) {
dp[i] = 1;
}
for (int i = 2; i <= n; ++i) {
ndp[0] = (dp[1] + dp[2] + dp[4]) % mod;
ndp[1] = (dp[0] + dp[2]) % mod;
ndp[2] = (dp[1] + dp[3]) % mod;
ndp[3] = dp[2];
ndp[4] = (dp[2] + dp[3]) % mod;
System.arraycopy(ndp, 0, dp, 0, 5);
}
long ans = 0;
for (int i = 0; i < 5; ++i) {
ans = (ans + dp[i]) % mod;
}
return (int)ans;
}
}
