题解 | #斐波那契数列#

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型
     */
     //记忆化搜索
    int dfs (int i, vector<int>& mem)
    {
        if (i == 1 || i == 2) return 1;
        //如存在记录dp[i]--直接返回对应值
        if ( mem[i] != -1) return mem[i];
        int count = dfs(i - 1, mem) + dfs(i - 2, mem);
        mem[i] = count;
        return count;

    }
    int Fibonacci(int n) {
        vector<int> mem(n + 1, -1);
        return dfs(n, mem);
        // write code here
    }
};