统计字典序元音字符串的数目【LC1641】
给你一个整数
n，请返回长度为n、仅由元音 (a,e,i,o,u) 组成且按 字典序排列 的字符串数量。字符串
s按 字典序排列 需要满足：对于所有有效的i，s[i]在字母表中的位置总是与s[i+1]相同或在s[i+1]之前。
思路
- 首先字符串只能包含5个元音字母，并且必须按照字典序排列，此时字母是什么其实不重要，重要的是上一个构造的字母是什么，接下来的字母必须在其之后的字母中选择（包括其）。因此在构造时只需记录上一个字符是第一个字符即可
class Solution { int[][] dp; public int countVowelStrings(int n) { dp = new int[n + 1][5]; for (int i = 0; i <= n; i++){ Arrays.fill(dp[i], -1); } return dfs(n, 0, 0); } public int dfs(int n, int index, int ch){ if (index == n) return 1; if (dp[index][ch] >= 0) return dp[index][ch]; int res = 0; for (int i = ch; i < 5; i++){ res += dfs(n, index + 1, i); } if (dp[index][ch] == -1){ dp[index][ch] = res; } return res; } }
class Solution { public int countVowelStrings(int n) { int[] f = {1, 1, 1, 1, 1}; for (int i = 0; i < n - 1; ++i) { int s = 0; for (int j = 0; j < 5; ++j) { s += f[j]; f[j] = s; } } return Arrays.stream(f).sum(); } } 作者：ylb 链接：https://leetcode.cn/problems/count-sorted-vowel-strings/solutions/2196576/python3javacgo-yi-ti-shuang-jie-ji-yi-hu-vh2j/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
