# LeetCode题目：Decode Ways，一维动态规划

By | 2012 年 9 月 16 日

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.

```class Solution {
public:
int numDecodings(string s) {
if(s.size() == 0)
return 0;
if(s.size() == 1 && s[0] != '0')
return 1;
if(s[0] == '0')
return 0;
int fix = s.size() == 2 ? 1: 0;
if(s[0] == '1' || (s[0] == '2' && s[1] <= '6'))
return numDecodings(s.substr(1)) + numDecodings(s.substr(2)) + fix;
return numDecodings(s.substr(1));
}
};
```

```class Solution {
public:
int numDecodings(string s) {
if(s.size() == 0)
return 0;
vector ways(s.size() + 2,1);//多出来的两个作为占位符，避免程序内判断是否超过size
for(int i = s.size() - 1; i >= 0; --i)
{
//self
if(s[i] == '0')
ways[i] = 0;
else
ways[i] = ways[i+1];

//self and next
if( i + 1 < s.size() && ((s[i] == '1' || (s[i] == '2' && s[i + 1] <= '6')))) {
ways[i] += ways[i + 2];
}
}
return ways[0];
}
};
```

Code rewrite at 2013-1-4, not very nice

```class Solution {
public:
int numDecodings(string s) {
if (s.size() == 0) return 0;
if (s[0] == '0') return 0;
int *ways = new int[s.size()];
ways[0] = 1;
for(int ei = 1; ei < s.size(); ++ei) {
char last = s[ei - 1];
char cur = s[ei];
if(cur == '0') {
if(last == '1' || last == '2')
ways[ei] = ei > 1 ? ways[ei-2] : 1;
else {
delete ways;
return 0;
}
} else if(last == '1' || (last == '2' && cur <= '6')) {
ways[ei] = ways[ei-1];
ways[ei] += ei > 1 ? ways[ei-2] : 1;
} else {
ways[ei] = ways[ei-1];
}
}
int ret = ways[s.size() - 1];
delete ways;
return ret;
}
};
```