1641. Count Sorted Vowel Strings

1641. Count Sorted Vowel Strings

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

문제

풀이

n = 1일 때
a => "a"
e => "e"
i => "i"
o => "o"
u => "u"
개수 => [1, 1, 1, 1, 1]

n = 2일 때
a => "aa", "ae", "ai", "ao", "au"
e => "ee", "ei", "eo", "eu"
i => "ii", "io", "iu"
o => "oo", "ou"
u => "uu"
개수 => [5, 4, 3, 2, 1]

n = 3일 때
a => "aaa" "aae", "aai", "aao", "aau", "aee", "aei", "aeo", "aeu", "aii", "aio", "aiu", "aoo", "aou", "auu"
e => "eee", "eei", "eeo", "eeu", "eii", "eio", "eiu", "eoo", "eou", "euu"
i => "iii", "iio", "iiu", "ioo", "iou", "iuu"
o => "ooo", "oou", "ouu"
u => "uuu"
개수 => [15, 10, 6, 3, 1]

여기서 점화식을 구할 수가 있다.
n=(구하고자 하는 n값)
i=(0~4사이 값)
dp[n][i] = sum(dp[n-1]) - sum(dp[n-1][0:i])

해당 점화식을 코드로 구현한 것이다.

결과