动态规划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 项的值。

动态规划问题的特征：

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