有点意思的题目。用动态规划可以O(n)求解出来:a[i]代表子字符串string(0,i)的可能解码方式,a[i] = {a[i-1] or a[i-1]+a[i-2]}.
意思是如果string(i)不为0,至少a[i] == a[i-1],即一种解码方法是string{0,.....(i-1)}+string(i);
然后如果string{i-1,i}是合法的(注意合法概念,比如11,12,20,但04就不合法),那么a[i] = a[i-1]+a[i-2],即还有一种解码方法是string{0,.....(i-2)}+string{i-1,i}
另外值得注意是如果a[i]求出来为0,那就可以停止运行了,直接返回0,因为这个字符串没法被解码。
#include<iostream>......
阅读全文