-算法

动态规划（Dynamic Programming）是一种通过将复杂问题分解成更简单的子问题来解决的算法技术。在动态规划中，通过存储子问题的解并重复利用这些解，来避免重复计算，从而提高算法的效率。

动态规划通常包含以下步骤：

1. 定义状态：确定问题的状态，即原问题和子问题中变化的量。
2. 设置状态转移方程：找出问题的状态之间的关系，建立状态转移方程来表示这种关系。
3. 初始化：对初始状态进行初始化。
4. 递推计算：按照状态转移方程进行递推计算，求解问题的最优解或最优值。
5. 输出结果：根据问题要求，输出最终的结果。

动态规划常常用于解决最优化问题，如最长递增子序列、背包问题、编辑距离等。一个经典的动态规划问题是斐波那契数列，下面是一个使用动态规划解决斐波那契数列的示例：

def fibonacci(n):
    if n <= 1:
        return n

    dp = [0] * (n + 1)
    dp[1] = 1

    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

    return dp[n]

# 测试
print(fibonacci(5))  # 输出：5

在上面的示例中，通过使用动态规划的思想，我们可以避免重复计算斐波那契数列中的子问题，从而以更高效的方式计算出第 n 个斐波那契数。动态规划是一种非常强大且常用的算法设计技术，在解决各种问题时都有广泛的应用。