基本的动态规划模型与经典例题代码

动态规划是一种解决问题的有效算法思想，通过将原问题分解成相互重叠的小问题，并存储每个子问题的解，避免了不必要的重复计算。基本的动态规划模型包括以下几个关键部分：

1. **定义状态**：明确问题中需要求解的目标变量，例如背包问题中可能的状态是“物品i在容量限制下的最大价值”。

2. **定义状态转移方程**：描述如何由一个子问题的解推导出另一个子问题的解，比如0-1背包问题中，状态转移可能为`dp[i][w] = max(dp[i-1][w], dp[i-1][w-w_i] + val_i)`。

3. **边界条件**：初始化一些基本情况的解，通常是最小、最大值或者容易处理的情况。

4. **填充表格**：按照状态转移方程，自底向上逐层计算所有状态的值。

5. **返回结果**：最后的结果往往是在整个表格的某个位置得到的。

经典的动态规划例题有多种，比如斐波那契数列、最长公共子序列、背包问题（如0-1背包、完全背包等）、最短路径问题（如Dijkstra算法的简化版）。这里以Fibonacci数列为例，这是一个很直观的动态规划应用：

def fibonacci(n):
    # 边界情况
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    else:
        # 创建一个大小为n+1的数组，存储中间结果
        fib = [0] * (n + 1)
        fib[0], fib[1] = 0, 1
        
        # 通过循环计算并存储值
        for i in range(2, n + 1):
            fib[i] = fib[i - 1] + fib[i - 2]
        
        # 返回第n个Fibonacci数
        return fib[n]

# 测试
print(fibonacci(6))  # 输出: 8