【在线编程产品介绍】
阿里云开发者社区在线编程：
免费刷题大神器，助你拿到好offer
周赛月赛不停歇，做题还能领奖品
大赛笔试全真题，常做常新有惊喜
点击链接开始产品体验：https://developer.aliyun.com/coding
本文为大家介绍的是“55.斐波那契字符数”的解法探究。先来看一下题目内容：
题目详情：
等级：中等
知识点：递归、剪枝
Tom发现了一种神奇的字符串-斐波那契字符串,定义f[1]=0,f[2]=1,对于所有的i>2都有f[i]=f[i-2]+f[i-1]，其中“+”代表拼接，比如01+10=0110，现在对于字符串f[n]，请判断f[n]的第k项是0，还是1。
输入两个数字n和k(n<=300,k<=1000000000)。
输出f[n]的第k位，如果k大于f[n]的位数，则输出-1。
本题在答题过程中很多小伙伴反应会出现超内存的现象，导致JVM崩溃。但其实这道题目是不可以暴力解题的，首先来看一下一般思路解法。
方法1：直接法（超时并超出内存限制）
这是一道找规律的题目，最简单的想法可以是自底向上地构建出从第一个字符串f[1]直到最后的f[n]，然后查看f[n]的第k项是0还是1。
由于斐波那契数递增速度非常快，当n较大时，这种暴力拼接法无法完成。
下面介绍一种优化的算法。
方法2：找规律（提交通过）
本题应充分利用斐波那契数列的性质，自顶向下对问题逐步剪枝，定位需要判断的数字位置。
比如，对输入n=19, k=98：
- 先算出n=19对应的字符串长度len，也就是斐波那契数列的第19项。考虑到k是int类型，故可以先算出n=1~47对应的斐波那契数组成的数组（n=47时，斐波那契数大于2^31-1，无需再提前计算更多的斐波那契数），然后直接在计算好的斐波那契数组中取出第19项。
- 找到n-2=17，n-1=18对应的斐波那契字符串长度（也就是第17/18个斐波那契数）len1，len2。同样也是在提前计算好的斐波那契数组中找到。
- 对于k=98，如果k>len1，说明要找的数字在n=18对应的斐波那契字符串中，也就是n=19对应的斐波那契字符串的后半部分；如果k<=len1，说明要找的数字在n=17对应的斐波那契字符串中，也就是n=19对应的斐波那契字符串的前半部分。
- 根据判断结果，将n赋值为n-2或n-1，同时将k赋值为k或(k-len1)，完成剪枝。回到第1步，递归向下搜索。直到n=1或者2，这时k也变为1，定位完成，结束递归，直接返回结果。
进一步优化：
当输入的n > 47时，斐波那契字符串的长度超出了int型变量k的表示范围。需要提前进行推断剪枝。你能根据k的int表示范围（小于等于2^31-1）这一特性，对n较大的那些用例进行优化么？
方法3：递归
这个问题可以使用递归的方法来求解。
题目中给出了字符串拼接的规律：f[i]=f[i-2]+f[i-1]。可以看出对于第i个字符串，它的前半部分属于第i-2个字符串，后半部分属于第i-1个字符串。
这样，当给定具体的n和k时，我们可以首先判断k位于第n个字符串的前半部分还是后半部分，然后递归的把k传递给第n-2或n-1个字符串。
计算过程：
- 为了判断属于前半部分还是后半部分，需要计算每一个字符串的长度。
一个len数组。每个位置为对应字符串的长度。
len[1] = len[2] = 1;
len[i] = len[i-2]+len[i-1];
- 如果k > len[n]，则输出-1。
- 设置递归函数 int find(int i, int k);这个函数返回第i个字符串中k个位置的字符
- 判断k在前半部分还是后半部分。
a) K <= len[i-2] 前半部分，调用find(i-2, k)
b) K > len[i-2] 后半部分，调用find(i-1, k-len[i-2])
上面的计算在第一步时会遇到问题，当n大于几十的时候，len就会超出int的范围。
对这个问题的解决基于对递归过程的观察，第4步a）中k始终是不变的，i的奇偶性也保持不变。所以在计算第1步len时可以提前停止，当发现len[i]>=k且i与n的奇偶性相同时。第4步中的递归起始也可以使用第i个字符串开始，而不是第n个。
时间复杂度O(2*n)
空间复杂度O(n)
是不是感觉有思路了，立刻点击这里开启答题！
算法题目的解法并不唯一，这里介绍部分解题思路给大家，希望可以给大家启发~
在线编程周赛、月赛火热进行中，更有限时答题活动，社区定制卫衣、双肩背包等你来拿~每天都有好礼相送~点击了解周赛详情：在线编程内测中，抢先周赛赢好礼！面试考试前，快来刷刷题！