Decode Ways [leetcode] DP

Decode Ways [leetcode] DP

題目：求將數字字符串s轉換成字母有多少種可能的結果？

dp(i)：s[0...i-1]可能的結果數。我們設si = i-1

分析s[si]：

1. s[si - 1] = '1' || s[si - 1] = '2' && s[si] = '6'

s[0...si]可以轉換成s[si]對應的字母 + s[0...si-1]對應的字母，也可能是 s[si-1..si]對應的字母 + s[0...si-2]對應的字母

即dp(i) = dp(i -1) + dp(i - 2)

2. s[si] = '0' 這個情況比較容易被忽略

2.1 s[si - 1] = '1' || s[si - 1] = '2'

s[0...si]可以轉換成s[si-1...si]對應字母 + s[0...si-2]對應的字母

dp(i) = dp(i - 2)

2.2 s[si - 1]不存在或者為其他數字

dp(i) = 0;

3.其他情況

dp(i) = dp(i-1)

代碼如下

    int numDecodings(string s) {
        vector dp(s.size() + 1);
        dp[0] = 1;
        int i = 1;
        for (; i <= s.size(); i++)
        {
            int si = i - 1;
            if (s[si] == '0')
            {
                if (si - 1 >= 0 && (s[si - 1] == '1' || s[si - 1] == '2'))
                    dp[i] = dp[i - 2];
                else
                    dp[i] = 0;
            }
            else if (si - 1 >= 0 && s[si - 1] == '1' || s[si - 1] == '2' && s[si] <= '6')
                dp[i] = dp[i - 1] + dp[i - 2];
            else
                dp[i] = dp[i - 1];
        }
        return s.size() == 0 ? 0 : dp[s.size()];
    }