如何快速来一套苹果全家桶 _数字

答案很简单，那就是赶紧刷好跳个槽加个薪，电子产品什么的不在话下，哈哈。
好了，让我们继续刷吧。
如果给你一个找规律的题目1,2,3,5,? 下一个是多少？
大家在读书时肯定遇到过这样找规律的题目，聪明的你肯定会知道下一个数字是8 ，为什么呢？这其实就是著名的斐波那契数列，下一个数字是前两个数字的和。
本质上的第91号题目 Ways其实就是斐波那契数列数列的变型，这是个什么样的题目呢？
大写字母A-Z被映射到了以下数字：
'A' -> 1'B' -> 2...'Z' -> 26
那么给定一个只包含数字的字符串，问这个数字字符串有多少种可能的解释。
比如给定“12” ，那就有两种解释，可以解释为AB也就是(1, 2) ，也可以解释为L ，即（12）。
该怎么解决这个问题呢？
思考过程
给定一个字符串假设是“1226” ，我们可以先从最简单的情况开始，从右边数第一个数字是6 ，那么对于数字6来说很简单，只有一种解释，那就是6 ，即：

文章插图
我们用“数组下标：{编码数字}”的形式来表示以某一个位置为开始的字符串所有可能的编码形式。
接下来我们来到了右数第二个数字2 ，对于26来说有两种解释，一种就是26也就是Z；另一种是(2,6)也就是BF ，因此：
【如何快速来一套苹果全家桶】

文章插图
这样我们来到了右数第三个数字，如果前两个我们可以很直观的“看出”答案的话，那么第三个数字所有可能的编码就不是那么直观了，显然我们需要某种策略，那么这个策略是什么呢？你能看出来吗？在往下读之前仔细想一想这个问题。
好啦，让我们来检查一下你想的是不是正确的(或者是不是已经困了) 。

文章插图
这里的策略就是要想知道第三个数字所有可能的编码形式我们必须借助前两个数字所有的编码形式，那这是什么意思呢？
对于右数第三个数字来说，我们可以将其解释为2 ，那么这时我们就必须依赖右数第二个数字形成的编码格式，从上图我们已经知道了该数字能形成的编码格式为{26},{2,6} ，因此我们只需要将右数第三个与{26} ， {2,6}合并就可以了，如图所示：

文章插图
对于右数第三个数字来说除了可以解释为2 ，我们还可以解释为22 ，如果解释为22 ，那么我们就必须依赖于右数第一个数字锁形成的编码格式，也就是{6} ，即：

文章插图
也就是说对于右数第三个数字来说所有可能的解释是{2,2,6}、{2,26}、{22,6} ，如图所示：

文章插图
现在你该知道怎么分析了吧，接下来我们来到了右数第四个数字1 ，基于上述讨论自己推导一下已1为开头的数字有多少种可能的解释。