91. 解码方法
程序员文章站
2022-07-16 10:22:00
...
方法一:动态规划
class Solution {
public:
int numDecodings(string s) {
if(s.empty() || s[0]=='0') return 0;
//状态:dp[i]表示以i结尾的字符串编码方法总数
int dp[s.size()]={0};
//初始化
if(s.size()>0 && s[0]!='0')
dp[0]=1;
if(s.size()>1){
if((s[0]=='1' && s[1]!='0') || (s[0]=='2' && s[1]>='1' && s[1]<='6'))
dp[1]=2;
else if(s[1]=='0' && s[0]>'2')
return 0;
else
dp[1]=1;
}
//转移方程
for(int i=2;i<s.size();i++){
if(s[i]=='0'){
if(s[i-1]=='1' || s[i-1]=='2')
dp[i]=dp[i-2];
else
return 0;
}
else if(s[i-1]=='1')
dp[i]=dp[i-1]+dp[i-2];
else if(s[i-1]=='2' && s[i]>='0' && s[i]<='6')
dp[i]=dp[i-1]+dp[i-2];
else
dp[i]=dp[i-1];
}
return dp[s.size()-1]; //结果
}
};
上一篇: HDU - 1158
推荐阅读
-
mysql取得datetime类型的数据,后面会跟个.0的实现方法
-
MAC下Mysql5.7.10版本修改root密码的方法
-
计算机二级考试MySQL常考点 8种MySQL数据库设计优化方法
-
steam如何快速切换账号?steam切换吃鸡游戏账号的方法介绍(附Steam账号切换器)
-
Steam提示fatal Error怎么办?Steam提示fatal Error的解决方法
-
超简单的qps统计方法(推荐)
-
Win10怎么关闭通知栏信息?Win10关闭通知栏信息的方法
-
Java实现获取银行卡所属银行,验证银行卡号是否正确的方法详解
-
Win10怎么屏蔽Win键?Win10系统屏蔽Win键的方法
-
php让json_encode不自动转义斜杠“/”的方法