leetcode

509.斐波那契数

力扣链接

动规五部曲

1. 确定用作状态转移的dp数组的下标及含义 dp[i]表示第i个斐波那契数的值
2. 动规核心 状态转移方程/递推公式 dp[i] = dp[i-1]+dp[i-2]
3. dp数组如何初始化 dp[0] = 0, dp[1] =1
4. 确定遍历顺序 从前向后遍历
5. 打印dp数组用于排错

动态规划—空间优化

class Solution {
public:
    int fib(int n) {
        if (n <2) return n;
        // dp[i]含义：第i个数的斐波那契值
        std::vector<int> dp(2);
        dp[0] = 0, dp[1] = 1;
        for (int i = 2, sum; i<n+1; i++){// 1 1 2 3
            sum = dp[0]+dp[1];
            dp[0] = dp[1];
            dp[1] = sum;
        }
        return dp[1];
    }
};

动态规划

class Solution {
public:
    int fib(int n) {
        if (n <2) return n;
        // dp[i]含义：第i个数的斐波那契值
        std::vector<int> dp(n+1); // 算上0有n+1个数
        dp[0] = 0, dp[1] = 1;
        for (int i = 2; i<n+1; i++) dp[i] = dp[i-1]+dp[i-2];
        return dp[n];
    }
};

递归

class Solution {
public:
    int fib(int n) {
        if (n < 2) return n;
        return fib(n-1) + fib(n-2);
    }
};

This site is open source. Improve this page.