(DP, Medium) Decode Ways

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

숫자는 한자리가 될 수도, 두 자리가 될 수도 있다.

기본적인 아이디어는 dp[i]에
두 자리로 가능한 경우 dp[i - 2]의 값을 누적하고,
한 자리로 가능한 경우 dp[i - 1]의 값을 누적한다.

다만, 중요한 것은 두 경우가 다 가능할 수 있기 때문에 (예를 들어 11) else 또는 else-if 처리하지 않고 케이스를 태우는 것이다.

dp배열 초기값 세팅에 아이디어가 부족해서 고민을 하다 시간 오바되어 솔루션 참고했다.
i - 2를 보장해야 하기 때문에 기본적으로 2개 인덱스에 초기값을 넣어주면 되는 것 같다.

참고- 숫자 변환 방법이야 여러가지가 있겠지만 string안의 캐릭터가 모두 숫자라는 점을 이용해서 char - '0' 해서 변환했다.

O(n) 시간복잡도를 가진다.

class Solution {
    public int numDecodings(String s) {
        if (s.charAt(0) == '0') return 0;

        int n = s.length();
        int[] dp = new int[n + 1];

        dp[0] = 1;
        dp[1] = 1;

        for (int i=2; i<=n; i++) {
            int onesDigit = s.charAt(i - 1) - '0';
            int tensDigit = (s.charAt(i - 2) - '0') * 10 + onesDigit;

            if (tensDigit >= 10 && tensDigit <= 26) {
                dp[i] = dp[i] + dp[i - 2];
            }

            if (onesDigit >= 1 && onesDigit <= 9) {
                dp[i] = dp[i] + dp[i - 1];
            }
        }

        return dp[n];
    }
}