斐波那契数列

Posted on In Views: Waline: Views: Symbols count in article: 367 Reading time ≈ 1 mins.

题解方法

  • 动态规划
  • 记忆化搜索

动态规划

$$
F(n) = F(n-1) + F(n-2)
$$

记忆化搜索

  • 存储计算值，供后续计算使用，避免重复计算

核心代码

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
private int calculate(int n) {
    if (n < 2) {
        return n;
    }
    // 若缓存中已有计算值，则直接返回
    if (cache[n] != 0) {
        return cache[n];
    }
    // 计算并缓存
    cache[n] = (calculate(n - 1) + calculate(n - 2)) % MOD;
    return cache[n];
}

记忆化搜索

1
2
// 共享缓存
private static int[] cache = new int[N];

题目来源

剑指 Offer 10- I. 斐波那契数列 - 力扣（LeetCode）