LeetCode-91.Decode Ways

A message containing letters from  A-Z  is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.
For example, Given encoded message  "12" , it could be decoded as  "AB"  (1 2) or  "L"  (12).
The number of ways decoding  "12"  is 2.
폭력 해법

public int NumDecodings(string s)
        {
            if (s.Length == 0)
                return 0;
            if (s.Length ==1&&s[0]!='0')
                return 1;
            if (s[0] == '0')
                return 0;
            int tmp = s.Length == 2 ? 1 : 0;
            if (s[0] == '1' || (s[0] == '2' && s[1] < '7'))
                return NumDecodings(s.Substring(1)) + NumDecodings(s.Substring(2)) + tmp;
            return NumDecodings(s.Substring(1));
        }

동적 계획:
현재 숫자가 0이면 앞의 숫자는 반드시 1 또는 2이어야 한다. 그렇지 않으면 인코딩 변환을 할 수 없다. 이때 앞의 1 또는 2와 함께 인코딩을 할 수 있기 때문에res[i]=res[i-2];만약 앞의 숫자와 앞의 숫자의 조합이 2가지 인코딩(분리 또는 함께 포함)을 할 수 있다면res[i]=res[i-1]+res[i-2];그렇지 않으면 현재 숫자는 단독으로 인코딩 변환을 해야 합니다.res[i] =res[i-1].

 public int NumDecodings(string s)
        {
            if (s.Length == 0 || s[0] == '0')
                return 0;
            int[] res = new int[s.Length + 1];
            res[0] = res[1] = 1;
            for (int i = 2; i <= s.Length; i++)
            {
                if (s[i-1]=='0')
                {
                    if (s[i - 2] == '1'|| s[i - 2] == '2')
                    {
                        res[i] = res[i - 2];
                    }
                    else
                    {
                        return 0;
                    }
                }
                else
                {
                    res[i] = res[i - 1];
                    if (s[i-2]!='0')
                    {
                        int val = (s[i - 2] - '0') * 10 + s[i - 1] - '0';
                        if (0 < val && val < 27)
                            res[i] += res[i - 2];
                    }
                }
            }
            return res[s.Length];
        }

DP 방법이 개선되었습니다.res 그룹을 세 개의 int로 바꾸면 충분합니다
되다듬다

 public int NumDecodings(string s)
        {
            int n = s.Length;
            if (n == 0) return 0;

            int[] res = new int[n + 1];
            res[n] = 1;
            res[n - 1] = s[n - 1] == '0' ? 0 : 1;

            for (int i = n - 2; i >= 0; i--)
                if (s[i] != '0') 
                   res[i] = (Convert.ToInt16((s.Substring(i,2))) < 27) ? res[i + 1] + res[i + 2] : res[i + 1];

            return res[0];
        }