牛客刷题-解密

描述

一条仅包含字母‘A’-‘Z’的消息用下列的方式加密成数字

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

现在给出加密成数字的密文，请判断有多少种解密的方法

例如：

给出的密文为“13”，可以解密为"AC"(1 3) 或者"M"(13).

所以密文"13"的解密方法是2种.

求解：

其实这题一看用递归就很简单，但是用dp会更快点
状态转移方程：dp[i]=dp[i-1]+dp[i-2] | dp[i-1]。

代码：

 1 class Solution {
 2 public:
 3     /**
 4      * 
 5      * @param s string字符串 
 6      * @return int整型
 7      */
 8     // 状态：dp[i]表示到第i个字母时的排列数量
 9     // 转移方程：记得容易用递归解决的问题，从递归的角度去考虑
10     // dp[i]=dp[i-1]+dp[i-2] | dp[i-1]
11     int numDecodings(string s) {
12         if(s.empty() || s[0]=='0'){
13             return 0;
14         }
15         vector<int> dp={1,1};
16         for(int i=1;i<s.size();++i){
17             if(s[i]=='0' && (s[i-1]-'0')>2){
18                 return 0;
19             }
20             if((s[i-1]-'0')*10+(s[i]-'0')>26 || s[i]=='0' || s[i-1]=='0'){
21                 dp.push_back(dp[i]);
22             }else{
23                 dp.push_back(dp[i-1]+dp[i]);
24             }
25         }
26         return dp.back();
27     }
28 };

tip:20行那里想了很久，两个数字组合，什么时候只有一种字母表示方法呢？

　　=》相加大于26；后面一个为0，这时候必须和前一个数字合并；前一个为0，这时候不能和后一个数字组合（逆向思维不够）。

心之所愿，永不相忘