剑指Offer46.把数字翻译成字符串

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

/* *动态规划题 *解题思路： *1.将字符的每一位求出来保存在数组里 2.dp[n] = mdp[n-2] + dp[n-1] (当第n个数能与第n-1个数组合成新的数,m=1,否则m=0) */

int translateNum(int num)
    {
          
   
        
        deque<int> v;
        while (num)
        {
          
   
            v.push_front(num % 10);
            num /= 10;
        }
        vector<int> dp;
        //dp.reserve(v.size());
        if (v.size() > 1)
        {
          
   
            dp.push_back(1);
            if (v[0] * 10 + v[1] <= 25)
            {
          
   
                dp.push_back(2);
            }
            else
            {
          
   
                dp.push_back(1);
            }
            for (int i = 2; i < v.size(); i++)
            {
          
   
                if (v[i-1]*10 +v[i] <= 25 && v[i-1]!=0)
                {
          
   
                    dp.push_back(dp[i - 1] + dp[i - 2]);
                }
                else
                {
          
   
                    dp.push_back(dp[i - 1]);
                }
            }
            return *(--dp.end());
        }
        else
        {
          
   
            return 1;
        }


    }

难点还是在于找规律：数学归纳法