# Leetcode91. Decode Ways（动态规划）

## Leetcode91. Decode Ways（动态规划）

• Medium
• Accepted：245,933
• Submissions：1,116,585

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

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

Given a non-empty string containing only digits, determine the total number of ways to decode it.

Example 1:

Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).

Example 2:

Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

### 链接

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

### 题解

                        112213

12213                    2213

2213        213           213            13

213    13      13   3     13   3        3  ""

13   3  3  ""  3  ""      3  ""

3  ""

$dp[i] = dp[i] + dp[i - 1] \ , \ s[i-1] \in [1, 9]$

$dp[i] = dp[i] + dp[i - 2] \ , \ s[i-2,i-1] \in [10, 26]$

### 代码

• Runtime: 8 ms, faster than 35.43% of C++ online submissions for Decode Ways.
• Memory Usage: 8.6 MB, less than 20.00% of C++ online submissions for Decode Ways.
class Solution {
public:
int numDecodings(string s) {
int n = s.length();
vector<int> dp(n + 1, 0);
dp[0] = 1, dp[1] = (s[0] == '0') ? 0 : 1;
for (int i = 2; i <= n; ++i)
{
if (s[i - 1] != '0')
dp[i] += dp[i - 1];
if (s[i - 2] == '1' || (s[i - 2] == '2' && s[i - 1] <= '6'))
dp[i] += dp[i - 2];
}
return dp[n];
}
};

// O(1) space

class Solution {
public:
int numDecodings(string s) {
int n = s.length();
int prev1 = 1, prev2 = (s[0] == '0') ? 0 : 1;
int ans = prev2;
for (int i = 2; i <= n; ++i)
{
ans = 0;
if (s[i - 1] != '0')
ans += prev2;
if (s[i - 2] == '1' || (s[i - 2] == '2' && s[i - 1] <= '6'))
ans += prev1;
prev1 = prev2;
prev2 = ans;
}
return ans;
}
};

The end.
2019年3月31日 星期日