中级编程通关练习题 #10 – 递增数列

给定一个全部是数字的字符串,检查里面的数字是否包含一个递增数列。一个递增数列就是从第三个数字开始,每个数字都是前面两个数字之和。譬如,字符串 “123581321”里面就包含一个递增数列:1、2、3、5、8、13、21,因为 1+2 = 3, 2+3 = 5,5+8 = 13, 8+13 = 21。

输入样例:

"230326294156250"

输出样例:

True

上面的输入样例的数字可以分割成下面的数列:2,30,32,62,94,156,250。从第三个数字开始,每个数字都是前面两个数字相加之和。所以输出结果是 True。

算法思路:

  • 可以采用递归回溯(backtrack)算法,从第三个数字开始检查,前面两个数字相加是否等于后面数字的开始数字。
  • 如果相等,则递归继续检查。如果不相等,则增加前面两个数字的长度,然后再次做检查。