[LeetCode] 1641.count-sorted-vowel-strings

⭐⭐ 문제

ttps://leetcode.com/problems/count-sorted-vowel-strings/ 💣

---

📌 문제 설명

• 주어진 정수 n에 대해, 길이가 n이고 모음 문자열로 이루어져 있으며 사전순으로 정렬된 문자열의 개수를 반환하는 문제
• Input: n = 1
  Output: 5
  Explanation: The 5 sorted strings that consist of vowels only are ["a","e","i","o","u"]
• Input: n = 2
  Output: 15
  Explanation: The 15 sorted strings that consist of vowels only are
  ["aa","ae","ai","ao","au","ee","ei","eo","eu","ii","io","iu","oo","ou","uu"].
  Note that "ea" is not a valid string since 'e' comes after 'a' in the alphabet.

📌 문제 풀이

dp 점화식으로 푸는 문제
1.dp = [1,1,1,1,1,1] 초기화 해준다. (n=1)
2. i : n = 2부터 n의 길이 까지 반복문
3. j : j = 3부터 순차적으로 이전 합을 더해준다

/**
 * @param {number} n
 * @return {number}
 */
var countVowelStrings = function (n) {
  let dp = [1, 1, 1, 1, 1];

  for (let i = 2; i <= n; i++) {
    for (let j = 3; j >= 0; j--) {
      dp[j] += dp[j + 1];
    }
  }
  return dp.reduce((a, b) => a + b);
};