LeetCode 509 Fibonacci Number

    
        标签：
        
            动态规划问题
        
    发布于：2022-02-14 12:52:21
    编辑于：2022-02-14 13:02:06
    浏览量：729

概述

https://leetcode.com/problems/fibonacci-number/

动态规划法（递归法）

base case：0 与 1
状态：n
选择：无
dp 函数 / 数组的定义：直接存储结果

代码：

class Solution {
public:
    array<int, 31> dp;
    int fib(int n) {
        for (auto& d : dp) d = -1;
        dp[0] = 0;
        dp[1] = 1;
        return helper(n);
    }
    
    int helper(int n) {
        if (dp[n] != -1) return dp[n];
        dp[n] = helper(n-1) + helper(n-2);
        return dp[n];
    }
};

动态规划法（迭代法）

下面这个会 RE：

class Solution {
public:
    int fib(int n) {
        vector<int> dp(n + 1, -1);
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i ++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
};

因为 n 可能为 0，导致 dp[1] 越界。

改正后：

class Solution {
public:
    int fib(int n) {
        if (n == 0) return 0;
        vector<int> dp(n + 1, -1);
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i ++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
};

进一步的空间优化：

class Solution {
public:
    int fib(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        int dpi2 = 0, dpi1 = 1, dpi;
        for (int i = 2; i <= n; i ++) {
            dpi = dpi1 + dpi2;
            dpi2 = dpi1;
            dpi1 = dpi;
        }
        return dpi;
    }
};

Links: leetcode-509-fibonacci-number