public class Node
{
public Node(long value, bool visited)
{
Value = value;
Visited = visited;
}
public long Value { get; set; }//存放结点的值
public bool Visited { get; set; }
}然后，我们就可以愉快地上DFS的栈写法啦
public static long Fblc(int n)
{
Stack<Node> s = new Stack<Node>();
s.Push(new Node(n, false));
long sum = 0;
long[] childrenResultMemo = new long[n+1];
childrenResultMemo[0] = 1;
childrenResultMemo[1] = 1;
//long children = 0;
while (s.Any())
{
var cur = s.Pop();
if (cur.Visited == false)
{
if (childrenResultMemo[cur.Value] == 0)
{
cur.Visited = true;
if (childrenResultMemo[cur.Value - 1] != 0 && childrenResultMemo[cur.Value - 2] != 0)
{
var result = childrenResultMemo[cur.Value - 1] + childrenResultMemo[cur.Value - 2];
childrenResultMemo[cur.Value] = result;
sum += result;
s.Push(cur);
}
else
{
s.Push(cur);
s.Push(new Node(cur.Value - 1, false));
s.Push(new Node(cur.Value - 2, false));
}
}
else
{
sum += childrenResultMemo[cur.Value];//保存子树结果的优化，会有个特殊情况要处理
}
}
}
return sum;
}上述算法的核心思想是，遍历栈，pop出栈顶元素，如果已经访问过（visited为true）,就跳过（上面代码由于采用了保存子树结果的优化，会有个特殊情况要处理，下文会详述）；否则，将当前父结点的visited标记为true，代表已访问过，并push到栈；然后将其子结点都push到栈。
如果按照这个思路，写出来的代码不会是上面那个样子的，代码量少得多也简洁得多，不过算法复杂度就会像递归写法差不多，因为存在重复计算。
那怎么办呢，解决办法只有一个，空间换时间，将子树的结果存起来，如果对应子树已经计算过有结果，就不再往下一层的深度遍历了，直接使用结果。我们将子树结果保存在了一个数组里面：
long[] childrenResultMemo = new long[n+1];
通常如果子树已经有结果，按逻辑来说应该就会被访问过。不过存在特例，就是一开始的子树0和子树1：
childrenResultMemo[0] = 1;
childrenResultMemo[1] = 1;
只需在这个特例的分支里面累加结果即可：
sum += childrenResultMemo[cur.Value];
怎么样，这种写法是不是很少见？其实斐波拉契数列的求值过程就像是树的深度优先遍历。所以只要是深度优先遍历的实现，完全就是可行的。
相关文章：
Python打印斐波拉契数列实例
PHP实现斐波那契数列
相关视频：
数据结构探险—队列篇
以上就是原来斐波拉契数列还有这种写法，你知道吗？的详细内容，更多请关注php中文网其它相关文章！
声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn核实处理。
程序员必备接口测试调试工具：点击使用
Apipost = Postman + Swagger + Mock + Jmeter
Api设计、调试、文档、自动化测试工具
网页生成APP，用做网站的技术去做APP：立即创建
手机网站开发APP、自助封装APP、200+原生模块、2000+映射JS接口按需打包
相关文章
相关视频
