动态规划

• 组合排序：dp[i]=dp[i-2] 单独排序：dp[i]=dp[i-1] 组合+单独排序：dp[i]=dp[i-1]+dp[i-2]
• 对于dp初始化为1，"10","20"要求初始化为1，可以考虑特殊处理
• 注意dp[i]是和0比较，不是和"0"

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 解码
     * @param nums string字符串 数字串
     * @return int整型
     */
    int solve(string nums) {
        // write code here
        // 单独排序 dp[i]=dp[i-1]
        // 除0外都可以单独
        // 组合排序 dp[i]=dp[i-2]
        // 组合加单独 dp[i]=dp[i-2]
        // nums[i-1]:1 nums[i] 0~9
        // nums[i-2]: 2 nums[i] 0~6
        vector<int> dp(nums.size()+1,1);
        if(nums=="0")
        {
            return 0;
        }
        if(nums=="10"||nums=="20")
        {
            return 1;
        }
        //dp[i-2]
        for(int i=1;i<nums.size();i++)
        {
            if(dp[i]==0)
            {
                dp[i+1]=0;
                continue;
            }
            if(nums[i]=='0')
            {
                //只能组合排序
                if(nums[i-1]=='1'||nums[i-1]=='2')
                {
                    
                    dp[i+1]=dp[i-1];
                }
                else{
                    dp[i+1]=0;
                }
            }
            else{
                //单独/组合1~9
                if(nums[i-1]=='1'||
                (nums[i-1]=='2'&&nums[i]<='6'&&nums[i]>='1'))
                {
                    // 单独+组合
                    dp[i+1]=dp[i]+dp[i-1];
                }
                else{
                    //单独
                    dp[i+1]=dp[i];
                }

            }
        }
        return dp[nums.size()];
    }
};