题目描述
一条包含字母 A-Z 的消息通过以下方式进行了编码：
'A' -> 1
'B' -> 2
...
'Z' -> 26
示例：
输入: "12"
输出: 2
解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。
输入: "226"
输出: 3
解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
题目链接： https://leetcode-cn.com/problems/decode-ways/
思路
使用动态规划求解。
- 状态定义：dp[i] 表示前 i 个字符（s[0:i-1]）的解码数，i ∈ [0, n]；
- 边界条件：dp[0] = 1（这一个很重要），dp[0] = 1（在 s[0]!='0' 的情况下）；
- 状态转移：
- dp[i] 表示前 i 个字符（s[0:i-1]）的解码数，所以我们要考虑 s[i-1] 以及之前的字符情况；
- 如果 s[i-1] = '0':
- 如果 s[i-2] = '1' 或者 s[i-2] = '2'，这样只能把 s[i-1] 和 s[i-2] 当成一个整体来看待（'10' 或者 '20'），这样的话解码数没有增加，也就是 dp[i] = dp[i-2]；
- 否则的话，无法解码，例如 '30' 或者 '40' 等，返回 0；
- 否则，如果 s[i-1] != '0':
- 如果 s[i-2]=='1'，这样无论 s[i-1] 为多少，都能进行两种解码：s[i-2]、s[i-1] 当做一个整体解码和两者分开解码，所以 dp[i] = dp[i-1] + dp[i-2]，dp[i-1] 对应分开解码，dp[i-2] 对应整体解码；
- 如果 s[i-2]=='2' 并且 s[i-1]<'7'，这样也可以进行两种解码（和上面一种情况一样），所以 dp[i] = dp[i-1] + dp[i-2]；
- 否则，上面两种情况都不满足，则 s[i-1] 只能单独解码，也就是 dp[i] = dp[i-1]；
由于 dp[i] 表示前 i 个字符（s[0:i-1]）的解码数，所以 dp 的长度为 n+1，最终返回 dp[n] 表示前 n 个字符的解码（str[0:n-1]）。
代码如下：
class Solution {
public:
int numDecodings(string s) {
if(s[0]=='0') return 0;
int n = s.size();
vector<int> dp(n+1, 0);
dp[0] = 1; // 注意要设为 1
dp[1] = 1;
for(int i=2; i<=n; i++){
if(s[i-1]=='0'){
if(s[i-2]=='1' || s[i-2]=='2') dp[i] = dp[i-2];
else return 0;
}else{
if(s[i-2]=='1' || s[i-2]=='2'&&s[i-1]<'7') dp[i] = dp[i-1] + dp[i-2];
else dp[i] = dp[i-1];
}
}
return dp[n];
}
};
- 时间复杂度：O(n)
- 空间复杂度：O(1)