[LeetCode] 91. Decode Ways (C++)

문제

 

https://leetcode.com/problems/decode-ways/

Decode Ways - LeetCode

 

풀이

 

난이도: Medium 

 

 

string에서 idx번째인 한자리 수만 알파벳으로 decode한다고 생각해보자.

이를 위해서는 [0~idx-1]까지가 decode가 가능해야한다.

만약 02에서 2를 B로 해석하면 앞의 0는 독립적으로 해석이 되어야 하지만 0은 decode가 불가능하다.

 

이번에는 idx-1과 idx번째를 두 자리 수로 취급하여 해석하는 경우를 생각해보자.

위의 이유와 동일하게 [0~idx-2]까지 decode가 가능해야 한다.

 

따라서 dp[idx]에 0~idx까지 decode가 가능한 경우의 수를 저장하면

dp[idx] = dp[idx-1] + dp[idx-2]가 된다.

 

단, 1~26 사이의 수만 decode가 가능하므로 범위를 확인해주자.

 

 

코드