不会飞的章鱼

熟能生巧，勤能补拙；念念不忘，必有回响。

剑指 Offer 10- I. 斐波那契数列

发表于 分类于
本文字数： 906 阅读时长 ≈ 1 分钟

题目

剑指 Offer 10- I. 斐波那契数列

我的复试：

题解

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//Java
class Solution {
    public int fib(int n) {
        //边界处理
        if (n == 0) return 0;

        //初始化数组dp
        int[] dp = new int[n + 1];

        //由于F(0) = 0，所以 dp[0] = 0
        dp[0] = 0;

        //由于F(1) = 1，所以 dp[1] = 1
        dp[1] = 1;

        //通过for循环来填充dp
        for (int i = 2;i <= n;i++) {
            //dp[i]的计算规则
            //F(N) = F(N - 1) + F(N - 2)
            dp[i] = dp[i-1] + dp[i-2];
            //答案需要取模 1e9+7 (1000000007)
            dp[i] %= 1000000007;
        }

        //返回结果
        return dp[n];
    }
}

leetcode-cn执行用时： 

1
2
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：38.4 MB, 在所有 Java 提交中击败了13.79%的用户
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//Go
func fib(n int) int {
    //边界处理
    if n == 0 {
        return 0
    }

    //初始化数组dp
    dp := make([]int,n+1)
    //由于F(0) = 0，所以 dp[0] = 0
    dp[0] = 0
    //由于F(1) = 1，所以 dp[1] = 1
    dp[1] = 1

    //通过for循环来填充dp
    for i := 2;i <= n;i++ {
        //dp[i]的计算规则
        //F(N) = F(N - 1) + F(N - 2)
        dp[i] = dp[i-1] + dp[i-2]
        //答案需要取模 1e9+7 (1000000007)
        dp[i] %= 1000000007
    }
    return dp[n]
}

leetcode-cn执行用时： 

1
2
执行用时：0 ms, 在所有 Go 提交中击败了100.00%的用户
内存消耗：1.8 MB, 在所有 Go 提交中击败了40.31%的用户
------ 本文结束------
如果本篇文章对你有帮助，可以给作者加个鸡腿~(*^__^*)，感谢鼓励与支持！