斐波那契数列动态规划写算法

斐波那契数列是一个经典的动态规划问题，它的每个数字都是前两个数字之和。动态规划通常用于优化递归算法，避免重复计算。下面是使用Python编写的一个简单的斐波那契数列动态规划算法：

def fibonacci_dp(n):
    # 创建一个长度为 n+1 的列表，用于存储已经计算过的斐波那契值
    fib_sequence = [0] * (n + 1)
    
    # 设置初始值
    fib_sequence[0], fib_sequence[1] = 0, 1

    # 使用循环从第二个数开始计算
    for i in range(2, n + 1):
        fib_sequence[i] = fib_sequence[i - 1] + fib_sequence[i - 2]
        
    return fib_sequence[n]

# 测试函数
n = int(input("请输入一个正整数: "))
result = fibonacci_dp(n)
print(f"斐波那契数列的第 {n} 项是: {result}")

相关问题

斐波那契数列动态规划写算法c语言

斐波那契数列是一个经典的动态规划问题，通常递归形式简单直观，但是效率较低，因为它会重复计算许多子问题。而通过动态规划，我们可以存储已经计算过的值以避免冗余计算。下面是一个使用C语言实现的斐波那契数列动态规划算法：

#include <stdio.h>

// 动态规划函数
int fibonacci(int n) {
    if (n <= 0) {
        return 0; // 0和负数的斐波那契数都是0
    }
    if (n == 1 || n == 2) {
        return 1; // 基本情况，前两个数都是1
    }

    int fib[n + 1]; // 创建数组保存中间结果
    fib[0] = 0;
    fib[1] = 1;

    for (int i = 2; i <= n; i++) {
        fib[i] = fib[i - 1] + fib[i - 2]; // 计算当前项等于前两项之和
    }

    return fib[n]; // 返回第n个斐波那契数
}

int main() {
    int n = 10; // 测试数字，你可以改变它
    printf("The %dth Fibonacci number is: %d\n", n, fibonacci(n));
    return 0;
}

斐波那契数列的动态规划算法的流程图

下面是斐波那契数列的动态规划算法的流程图：

1. 开始
2. 初始化数组f，其中f[0]为0，f[1]为1。
3. 初始化变量n为要生成的斐波那契数列的项数。
4. 如果n小于等于1，则返回f[n]。
5. 循环i从2到n，执行以下步骤：
a. 设置f[i]为f[i-1]+f[i-2]。
6. 返回f[n]。
7. 结束。

在这个算法中，我们使用了一个数组f来存储斐波那契数列中的每一项。我们首先初始化f[0]和f[1]，然后循环从第2项开始计算。在每一次迭代中，我们使用f[i-1]和f[i-2]的值来计算f[i]，然后将f[i]存储到数组中。最后，我们返回f[n]，即生成的斐波那契数列的第n项。

这个算法的时间复杂度为O(n)，因为我们只需要计算n次，每次计算都需要常量时间。另外，这个算法也可以使用递归实现，但是递归实现的时间复杂度为O(2^n)，因此不推荐使用。