https://www.acmicpc.net/problem/2011
initial
So dp is all about finding patterns. But I wasnt sure if it was a dp question so I tried finding the total number of possibilities by a simple for loop where we check 2 consecutive numbers. Nope didnt work.So let’s try to find out a pattern. If we can build upon the previous cases, it is dp. As you can see in the image, we can indeed do that. For example, 251 builds upon total combinations of 25 + adding 1 at the end and total combinations of 2 + adding 51 but since 51 is outside the alphabet range, we dont do that. But 2511 we can do total combinations of 251 + adding 1 at the end and combinations of 25 + add 11 (2 digit).
So there are 2 conditions. If the incoming digit is indeed between 1 to 9, then we can add the previous total combinations (dp[i-1]). And if the last digit of our current number + incoming digit that makes up 2 digit like 11 is in between 10 to 26, we can add the previous previous total combinations (dp[i-2]). One edge case we have to consider is that when i=0, we will get an indexoutofrange for checking 2 digit so we dont check the second condition. Also, if incoming digit is 0, first condition doesnt meet. We initialise dp starting values with dp[0]=1 and dp[1]=1.
solution
lst = list(map(int, input().rstrip()))
dp = [0 for _ in range(len(lst) + 2)]
dp[0] = 1
dp[1] = 1
for i in range(len(lst)):
if 1 <= lst[i] <= 9:
dp[i + 2] += dp[i + 1]
if i == 0:
continue
if 10 <= lst[i - 1] * 10 + lst[i] <= 26:
dp[i + 2] += dp[i]
print(dp[-1]%1000000)complexity
n time and space
