题目：

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.

思路：

这也是一个典型的DP问题，首先定义一个数组，dp[i]为到第i个字符所能组成的所有编码方式的个数。那么对于dp[i+1]来说，肯定至少和dp[i]一样多，如果第i个字符和i+1个字可以合成一个字符，那么dp[i+1] += dp[i-1]。不过这里需要注意的是违规字符。

?

#include 
  
   
#include 
   
     #include 
    
      using namespace std; int Decode_num(string& str) { vector
     
       vec(str.size(),0); if(str.size() <2) return 1; vec[0] =1; if(str[0]=='1' || str[1]<='6') vec[1] =2; int i; int tmp; for(i=2;i
      
       
?