LeetCode 509 Fibonacci Number

Tag: 动态规划问题 Posted on 2022-02-14 12:52:21 Edited on 2022-02-14 13:02:06 Views: 178

概述

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

动态规划法(递归法)

  1. base case:0 与 1
  2. 状态:n
  3. 选择:无
  4. 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;
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/