일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
Tags
- 컴퓨터의 구조
- Python
- LeetCode
- attribute
- Convert Sorted List to Binary Search Tree
- iterator
- DWG
- Class
- 시바견
- Generator
- 30. Substring with Concatenation of All Words
- t1
- 운영체제
- 프로그래머스
- Python Implementation
- Protocol
- 109. Convert Sorted List to Binary Search Tree
- data science
- 43. Multiply Strings
- 파이썬
- shiba
- kaggle
- Regular Expression
- Python Code
- Substring with Concatenation of All Words
- 715. Range Module
- concurrency
- 밴픽
- Decorator
- 315. Count of Smaller Numbers After Self
Archives
- Today
- Total
Scribbling
[Dynamic Programming] Practice Question 본문
Q: Find the number of unique strings of which the length is L, given that the maximum number of consecutive vowels allowed is K.
* There are 21 types of consonants and 5 types of vowels.
For example, L=4, K=1:
then allowed patterns are -
CCCC
CCCV, CCVC, CVCC, VCCC, VCVC, VCCV, CVCV
This question can be easily handled with DFS. However, the approach would not be optimal as it involves unnecessary calculations.
Why is that?
Let's say we calculated all the cases for L=3. The results of L=3 can be used for L=4. And this is why we use dynamic programming for this question.
What information should we store?
dp[i][j]: the number of unique strings of which the length is i and exactly j last letters are vowels.
Then,
import math
def solution(m, n):
if n == 0:
return int(math.pow(21, m)) % (10**9+7)
# dp[i][j]: # of words with length i with exactly last j letters are vowels
dp = [[0] * (n+1) for _ in range(m+1)]
dp[1][0] = 21
dp[1][1] = 5
for i in range(2, m+1):
for j in range(n+1):
if j > i: break
if j == i:
dp[i][j] = int(math.pow(5, i))
elif j == 0:
dp[i][j] = 21 * sum(dp[i-1][j] for j in range(n+1))
else:
dp[i][j] = 5 * dp[i-1][j-1]
return sum(dp[-1][j] for j in range(n+1))
print(solution(2, 1))
'Computer Science > Coding Test' 카테고리의 다른 글
LeetCode: 1101. The Earliest Moment When Everyone Become Friends (0) | 2023.09.14 |
---|---|
Overlapping Intervals/Ranges (0) | 2023.04.24 |
LeetCode: 2115. Find All Possible Recipes from Given Supplies (0) | 2022.05.03 |
LeetCode: 1032. Stream of Characters (0) | 2022.03.25 |
LeetCode: 2034. Stock Price Fluctuation (0) | 2022.03.23 |