第四十九题
动态规划，判断数字是否可以表示字母 的几种情况分类
知道一维数组怎么填
class Solution {
public:
    /**
     * 解码
     * @param nums string字符串 数字串
     * @return int整型
     */
    int solve(string nums) {
        // write code here
        int *dp=new int[nums.length()+1];
        // 初始化起始两个位置
        if(nums[0]>'0')
            dp[1]=1;
        dp[0]=1;
        
        // 后面开始动态规划
        for(int i=1;i<nums.length();i++){
            // 记录下前面一个数字个当前的数字
            int a=nums[i-1]-'0';
            int b=nums[i]-'0';
            // 两个数连起来是多大？
            int temp=a*10+b;
            // 先要判断当前的数字是否是0 如果是0，因为0不能表示字母，所以会产生特殊情况
            if(b==0)
            {
                // 如果说是0，且前面一个数属于26个字母中间 dp就和前面一个一样，因为0无法表示字母
                // 1120 看0，只有可能让20来表示第20个字母 那么 dp只能是前面11的所有种类的个数
                if(temp>=10 && temp<=26)
                    dp[i+1]=dp[i];
                else
                    // 如果说是0，且前面的数拼接起来不是字母 那么从此，后面永远不能表示出字符串
                    // 1219[0]123.... 看0，0在当中 和前面是90 没有字母 0也表示不了字母，所以结果错误，从此后面都是0了
                    dp[i+1]=0;
            }
            else{
                // 如果说不是0
                // 判断是否可以和前一个数组合起来？
                if(temp>=10 && temp<=26)
                    // 如果可以组合起来，则 当前的值应该是 排除前面一个的所有可能的个数 加上 包含前面一个的所有可能的个数
                    // 112[3]123...看3 23显然可能表示字母，如果说把23看成一个字，那就要向前看11可能组成的个数种类2；加上只把3看成c后向前看112可能的种类是3
                    dp[i+1]=dp[i-1]+dp[i];
                else// 如果不可以组合 那这个数只可能有一种情况 不会产生新的结果 所以直接复制前一项值
                    // 112[9]123...看9 29显然不能表示字母，结果就是112所有可以表示的种类加上9（i）,9只能用来表示第九个字母'i'，所以结果不会变多 就和前面112的可能结果一样
                    dp[i+1]=dp[i];
            }
        }
//         for(int i=0;i<=nums.length();i++)
//             cout<<dp[i]<<" ";
        return dp[nums.length()];
    }
};