题解 | #把数字翻译成字符串#

转载自：NC116把数字翻译成字符串_牛客博客
https://blog.nowcoder.net/n/c0a01037177b4775b632242d8dd02d73?f=comment
基本和上面的一样，这个题解作为自己的思考理解和复习用，感觉写还比较容易懂，欢迎大家交流！

// NC116把数字翻译成字符串
class Solution {
public:
    /**
     * 解码
     * @param nums string字符串 数字串
     * @return int整型
     */
    int solve(string nums) {
        // write code here
        /* 定义状态：
            dp[i]:以下标为i结尾的字符串的解码方式数
        状态转移：
            1、当nums[i]==0;由于0没有对应解码方式，只能和前一位nums[i-1]组合。且前一位只能为1或者2
                dp[i]=dp[i-2];(i>1) 因为最后两位如果能解码，那么它的解码数量取决dp[i-2]，因为最后两位固定了
                dp[i]=1;(i=1) 因为此时只有两位数，能解码的话就只有一种方式
            2、当nums[i]!=0;
                分析2.1、当nums[i-1]为1的时候，满足要求
                分析2.2、当nums[i-1]为2的时候，判断下nums[i]是否在1-6之间，因为>26的数无法解码
                dp[i]=dp[i-1]+dp[i-2];//因为在11-26之间(20在上面已经判断完了)，可以组合解码，也可以单个解码
            3、初始化
                dp[0]=1;
            4、结果返回
                dp[n-1];n为nums的长度
                 */

            //注意nums中的是字符，要注意字符转数字的方式    
        int len=nums.size();
        if(len==0) return 1;
        if(nums[0]=='0') return 0;
        vector<int>dp(len);
        dp[0]=1;
        for(int i=1;i<len;++i){
            // 如果是0结尾
            if(nums[i]=='0'){
                // 如果前一位是1或者2，也就是能组合解码
                if( nums[i-1]=='1' || nums[i-1]=='2' ){    
                    if(i==1) 
                        dp[i]=1;//如果只有两位
                    else
                        dp[i]=dp[i-2];
                }
                //如果前一位不是1或者2，那这串就解码不了，默认0    
            }else{
                //如果nums[i]!=0;
                if(  nums[i-1]=='1' || (nums[i-1]=='2' && nums[i]>='1' && nums[i]<='6' )  ){
                    if(i==1)
                        dp[i]=2;
                    else
                        dp[i]=dp[i-1]+dp[i-2];
                }else{
                    // 如果是其他条件，如果xxxx37;就只能拆开
                    dp[i]=dp[i-1];
                }
            }
        }
        return dp[len-1];
    }
};