fibonacci [1] mage ntc 缓存 img pub cci https
直接使用递归的方法会导致TLE,加个缓存就好了:
- public class Solution {
- private Integer[] buff = new Integer[1000];
- /*
- * @param n: an integer
- * @return: an ineger f(n)
- */
- public int fibonacci(int n) {
- if (buff[n] != null) return buff[n];
- else if (n == 1) return buff[1] = 0;
- else if (n == 2) return buff[2] = 1;
- else return buff[n] = fibonacci(n - 1) + fibonacci(n - 2);
- }
- }
或者使用迭代法:
- public class Solution {
- /*
- * @param n: an integer
- * @return: an ineger f(n)
- */
- public int fibonacci(int n) {
- if (n == 1) return 0;
- else if (n == 2) return 1;
- int a = 0,
- b = 1,
- c = a + b;
- n -= 2;
- while (n-->0) {
- c = a + b;
- a = b;
- b = c;
- }
- return c;
- }
- }
http://www.lintcode.com/zh-cn/problem/fibonacci/
LintCode题解之斐波纳契数列
fibonacci [1] mage ntc 缓存 img pub cci https
原文:http://www.cnblogs.com/cc11001100/p/7898180.html
来源: http://www.bubuko.com/infodetail-2407369.html