[LeetCode] 1641. Count Sorted Vowel Strings #Python

Given an integer n, return the number of strings of length n that consist only of vowels (a, e, i, o, u) and are lexicographically sorted.

A string s is lexicographically sorted if for all valid i, s[i] is the same as or comes before s[i+1] in the alphabet.

 

Example 1:

Input: n = 1

Output: 5

Explanation: The 5 sorted strings that consist of vowels only are ["a","e","i","o","u"].

 

Example 2:

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.

 

Example 3:

Input: n = 33 Output: 66045

 

Constraints:

• 1 <= n <= 50 

 

# 정답코드 : 

참조: bottom up 방식의 피보나치 수열 해결방법 참조 

memo = [0] * 101
n= 99

memo[1] = 1
memo[2] = 1

for i in range(3, n+1):
    memo[i] = memo[i-1] + memo[i-2]
print(memo[n])

 

# n번 반복 for문을 다이나믹으로 변환한 누적합 계산법 

def countVowelStrings( n ):
    dp = [0] + [1] * 5
    for i in range(1, n + 1):
      print(dp)
      for k in range(1, 6):
        dp[k] += dp[k - 1]
        
    print(dp)
    return dp[5]
    
    
 # Output
 
 countVowelStrings(3)

[0, 1, 1, 1, 1, 1]
[0, 1, 2, 3, 4, 5]
[0, 1, 3, 6, 10, 15]
[0, 1, 4, 10, 20, 35]
35

 

# 고민.. 

문제를 # output 과 같이 심플하게 수열로 정리하기가 힘들다. 

n번 반복 for문으로 이해되는 재귀적 문제에 대해서.. 수열적인 해결방법을 제시한다. 

다른 방법이 discussion에 많으므로 시간이 있을 때 탐색하고 정리할 필요가 있다. 

 

# ! 

for 문의 중첩으로 다룰 수 있는 수열들.. 에 대한 예시로 활용가능 할 듯 하다.