这个动态规划有点难,因为f(i)不仅与f(i-1)有关,和f(i-2)也有关系,能想明白这一层关系着实不容易0.0
设当前的解法有f(i)种,由于s[i]和s[i - 1]的搭配方式有多种,下面分情况讨论:
- 非法的情况,即不论怎么搭配都decode不了,返回0
- 合法的情况,如果只能搭配成一种,那么
f(i)=f(i-1)
,如果能搭配成两种,那么f(i)=f(i-1)+f(i-2)
class Solution { public: /** * * @param s string字符串 * @return int整型 */ int numDecodings(string s) { // write code here if(s.size() < 1 || s[0] == '0') return 0; int a = 1, b = 1, dp = 1; for (int i = 1; i < s.size(); ++i) { // 非法的情况 if (s[i] == '0' && (s[i - 1] > '2' || s[i - 1] == '0')) return 0; // 合法的情况之可拆 if (s[i] != '0' && ((s[i - 1] == '1') || (s[i - 1] == '2' && s[i] < '7'))) dp = a + b; // 合法的情况之不可拆 else dp = b; a = b; b = dp; } return dp; } };