링크 : https://leetcode.com/problems/count-sorted-vowel-strings/

description

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

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.

Input: n = 33
Output: 66045

Constraints

• 1 <= n <= 50

풀이

코드

class Solution:
    def countVowelStrings(self, n: int) -> int:
        dp = [1, 1, 1, 1, 1]

        for i in range(1, n):
            dp[0] += sum([dp[j] for j in range(1, 5)])
            dp[1] += sum([dp[j] for j in range(2, 5)])
            dp[2] += sum([dp[j] for j in range(3, 5)])
            dp[3] += sum([dp[j] for j in range(4, 5)])

        return sum(dp)

결과

Runtime: 24 ms, faster than 96.31% of Python3 online submissions for Count Sorted Vowel Strings.
Memory Usage: 14.5 MB, less than 13.42% of Python3 online submissions for Count Sorted Vowel Strings.

설명

사실 이 문제는… 고민하다가 힌트를 봐서 푼 문제다. 😅 정말 유레카 그 자체~ a로 시작하는 경우에는 경우의 수가 5, 4, 3, 2, 1이고 이 숫자에 대해 다시 5, 4, 3, 2, 1 | 4, 3, 2, 1 … (앞에서 먼저 계산했던 수들임)이 된다. 일단 1개씩 다 깔아두고 마지막 e로 시작하는 경우에는 항상 경우의 수가 1이 된다. 단순히 dp[1] + dp[2] 이런 식으로 표현할 수 있기는 하지만 inline for loop로 간단하게 나타내도록 했다. 정말 놀라운 DP의 세계 ㅠ