动态规划-斐波那契数列

阅读量: 257 编辑

初始状态

f[0] = 0;

f[1] = 1;

递推公式(状态转移方程)

f[n] = f[n-1] + f[n-2];

【参考程序】

//爱码岛编程
//使用数组记录状态转移 

int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }

    vector<int> dp(n + 1, 0); // 动态规划数组
    dp[0] = 0;
    dp[1] = 1;

    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}
爱码岛编程公众号
试卷资料
爱码岛编程小程序
在线刷题
苏ICP备13052010号
©2023 南京匠成信息科技有限公司