将数组拆分成斐波那契序列

题目描述

示例

代码如下：

public class SplitIntoFibonacci {LinkedList<Integer> res = new LinkedList<>();public List<Integer> splitIntoFibonacci(String num) {if(num.length() < 3) return res;if(dfs(num, 0)) return res;return new LinkedList<>();}public boolean dfs(String num, int start) {//边界条件判断，如果截取完了，并且res长度大于等于3，表示找到了一个组合。if (start == num.length() && res.size() >= 3) {return true;}for (int i = start; i < num.length(); i++) {//两位以上的数字不能以0开头if (num.charAt(start) == '0' && i > start) {break;}String s = num.substring(start, i + 1);//截取字符串转化为数字long cur = Long.valueOf(s);//如果截取的数字大于int的最大值，则终止截取if (cur > Integer.MAX_VALUE) {break;}int size = res.size();//如果截取的数字大于res中前两个数字的和，说明这次截取的太大，直接终止，因为后面越截取越大if (size >= 2) {if(cur > res.get(size - 1) + res.get(size - 2)){break;}if(cur < res.get(size - 1) + res.get(size - 2)){continue;}}//把数字cur添加到集合res中res.add((int) cur);//如果找到了就直接返回if (dfs(num, i + 1))return true;//如果没找到，就会走回溯这一步，然后把上一步添加到集合res中的数字给移除掉res.removeLast();}return false;}}