动态规划python简单例子-斐波那契数列

def fibonacci(n):
    dp = [0, 1] + [0] * (n - 1)  # 初始化动态规划数组

    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]  # 计算斐波那契数列的第 i 项

    print(dp)
    return dp[n]  # 返回斐波那契数列的第 n 项


# 示例用法
n = 10  # 计算斐波那契数列的第 10 项
result = fibonacci(n)
print(f"斐波那契数列的第 {n} 项是：{result}")

• 定义了一个名为?fibonacci?的函数，该函数接受一个整数?n?作为参数，并返回斐波那契数列的第?n?项。
• 我们使用一个动态规划数组?dp?来存储计算过程中的中间结果，其中?dp[i]?表示斐波那契数列的第?i?项。通过迭代计算?dp[i]?的值，
• 我们可以逐步计算出整个斐波那契数列的值。最后，我们返回?dp[n]，即斐波那契数列的第?n?项的值。

动态规划问题的特征：

• 最优子结构：问题的最优解包含子问题的最优解。
• 无后效性：即子问题的解被计算出来后，可以被保存起来以供后面子问题重复使用，不必重新计算。
• 重叠子问题：子问题之间存在相似或相同的情况，即存在重叠的子问题。

?