解码方法
解码方法
http://www.nowcoder.com/questionTerminal/b83b126603dd4e63bc4287d32d754886
题目难度：二星
考察点：动态规划
方法：动态规划
1.分析：
这是一道比较典型的动态规划问题，我们设dp[n]表示字符串前n个数字所有的解码方案，那么其实一共有26个英文字母，即对应着1-26这么多数字，而1-9是一位的，10-26是两位的，那么就存在如下两种情况：
a. 第n-2个数字和第n-1个数字组合起来的十进制数不超过26，那么此时dp[n] = dp[n-1] + dp[n-2]
b. 其它情况，dp[n] = dp[n-1]
所以有如下状态转移方程：
算法实现：
(1). 输入一个字符串s，初始化dp[0]=1。(2). 遍历字符串，然后根据上述状态转移方程，求dp[n]
(3). 输出dp[s.size()]
空间复杂度：O(n)
2.复杂度分析：
时间复杂度：O(n)空间复杂度：O(n)
3.代码：
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6+5;
int dp[MAXN];
int main(){
string s; cin>>s;
dp[0] = 1;
for(int i=1; i<=s.size(); i++) {
if(i>=2 && 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];
}
cout<<dp[s.size()]<<endl;
return 0;
} 
你cet6就cet6，cet4就cet4，你写个cet证书等是什么意思。专业技能快赶上项目行数，你做的这2个项目哪里能提现你有这么多技能呢
小米三面59人在聊