88>算法笔试模拟题精解之“斐波那契字符数”1.4剪枝算法笔试模拟题精解之“斐波那契字符数”贡献者 | 洪浩原简介：本题应充分利用斐波那契数列的性质，自顶向下对问题逐步剪枝，定位需要判断的数字位置。题目描述题目等级：中等知识点：递归、剪枝查看题目：斐波那契字符数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 崩溃。但其实这道题目是不可以暴力解题的，首先来看一下一般思路解法。算法笔试模拟题精解之“斐波那契字符数” <89方法 1：直接法（超时并超出内存限制）这是一道找规律的题目，最简单的想法可以是自底向上地构建出从第一个字符串f[1] 直到最后的 f[n