1641. Count Sorted Vowel Strings

[zeikar]

Problem link

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

Problem Summary

n 개의 모음을 이어 붙일 수 있다. 이때 사전 순으로 정렬된 문자열의 개수를 구하는 문제.

Solution

딱 보니 DP로 풀어야겠다는 생각이 든다.

DP[i][j] = i번째 인덱스에 j번째 모음으로 시작하는 문자열의 개수

로 두면 DP[i][j] = DP[i - 1][k] (0 <= k <= j)가 된다.

추가로 DP[i] 행은 계속 덮어 띄워지므로 1차원으로 줄일 수 있다. DP[j]: j번째 모음으로 시작하는 문자열의 개수

Source Code

class Solution:
    def countVowelStrings(self, n: int) -> int:
        dp = [1] * 5
        for i in range(1, n):
            dp[0] += dp[1] + dp[2] + dp[3] + dp[4]
            dp[1] += dp[2] + dp[3] + dp[4]
            dp[2] += dp[3] + dp[4]
            dp[3] += dp[4]

        return sum(dp)