leetcode每日一题36

91.解码方法

变形的蜗牛爬塔问题，动态规划 五部曲走起

确定dp数组及下标含义 f(n)代表当前在字符串的第n位时的解码方法数，而因为可以一次性分割（解码）1位或两位，那么在n位时，假设其上一位为a，当前位为b，前面为xxx xxxab，那么就可以分割为xxxa b和xxx ab 所以当前位的分割数相当于xxxa的分割数与xxx的分割数之和 方法数就是f(n-1)和f(n-2)的之和 同时，f(0)代表着空串的分割次数，所以f和字符串s的序号间应该差一位确定递推公式 f(n)=f(n-1)+f(n-2) 但有几种特殊情况 第0位不能为0 如果s(n-1)==0，也就是当前位=0，0不能被单独解码，所以不存在单独的在n位前的分割， 如果前一位为0，那么不可解码，返回0 如果前一位不为0，但是>2的数，如3，那么和前一位合起来就是30，也不能解码，返回0 如果前一位>0&&❤️，那么可以和前一位合起来解码 因此此时的解码方法数与xxx时相同，解码为xxx ab 则f(n)=f(n-2) 如果s(n-1)*10+s(n)>26，那么就不能分隔为xxx ab，只能分割为xxxa b 则f(n)=f(n-1) 这里主要是f和s总是差一位，所以有点绕 for(int i=2;i<s.length()+1;i++) { if(s[i-1]=='0'&&s[i-2]>'0'&&s[i-2]<'3') f[i]=f[i-2]; else if(s[i-1]=='0'&&(s[i-2]=='0'||s[i-2]>'2')) return 0; else if(s[i-2]=='1'||(s[i-2]=='2'&&s[i-1]<'7')) f[i]=f[i-1]+f[i-2]; else f[i]=f[i-1]; } 初始化 f(0)=1; f(1)=1;确定遍历顺序 从前往后举例推导

完整代码：

class Solution { public: int numDecodings(string s) { vector<int> f(s.length()+1,0); if(s[0]=='0') return 0; f[0]=1; if(s.length()==1) return 1; f[1]=1; for(int i=2;i<s.length()+1;i++) { if(s[i-1]=='0'&&s[i-2]>'0'&&s[i-2]<'3') f[i]=f[i-2]; else if(s[i-1]=='0'&&(s[i-2]=='0'||s[i-2]>'2')) return 0; else if(s[i-2]=='1'||(s[i-2]=='2'&&s[i-1]<'7')) f[i]=f[i-1]+f[i-2]; else f[i]=f[i-1]; } return f[s.length()]; } };

主要在f和s对齐的事情上纠结了很久，最后好不容易画图想明白了 下次这种事情还是得画一画 本来想能不能让f和s的序号一致的，后来发现还是不行，绕不出来 官解下面有位大佬给了思路：

当前位若不为 0，一定可以独立编码，所以 dp[i] = dp[i - 1]，然后再去考虑能不能后两位联合编码，后两位联合编码要满足两个条件：1.前一位不为字符 ‘0’; 2.这两位构成的数小于等于 26 。如果这两个条件都满足，就在原来的基础加上联合编码的种类 dp[i] += dp[i - 2]，等等！还要考虑越界的问题，也就是 i = 1 时怎么办 ？很简单，就是在前面的基础上加一，这个一指的就是后两位联合编码

粘一下他的代码：

public: int numDecodings(string s) { int n = s.size(); if (s[0] == '0') { return 0; } vector<int> dp(n); dp[0] = 1; for (int i = 1; i < n; ++i) { if (s[i] != '0') { dp[i] = dp[i - 1]; } if (s[i - 1] != '0' && (s[i - 1] - '0') * 10 + s[i] - '0' <= 26) { if (i > 1) { dp[i] += dp[i - 2]; } else { dp[i] += 1; } } } return dp[n - 1]; } };

哎，怎么到这个时候了还是这么菜