算法设计与分析基础 第八章

### 关于《算法设计与分析基础》第八章的内容总结和关键知识点

#### 8.1 动态规划简介
动态规划是一种通过把原问题分解成相对简单的子问题的方式来求解复杂问题的方法。这种方法主要用于优化问题，在计算过程中保存已解决的子问题答案，从而避免重复计算[^1]。

#### 8.2 动态规划的基本要素
- **最优子结构性质**：如果一个问题可以分解为若干个子问题，并且这些子问题之间存在重叠，则该问题具有最优子结构特性。
- **无后效性原则**：即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

#### 8.3 常见的应用场景
- **最长公共子序列 (LCS)**：给定两个字符串，找到它们之间的最长公共子串长度。
- **背包问题**：在有限容量下选择物品使得总价值最大化的经典组合优化问题。

def lcs_length(X, Y):
    m = len(X)
    n = len(Y)
    
    # 创建一个二维数组来存储中间结果
    c = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i - 1] == Y[j - 1]:
                c[i][j] = c[i - 1][j - 1] + 1
            else:
                c[i][j] = max(c[i - 1][j], c[i][j - 1])
                
    return c[m][n]

#### 8.4 复杂度分析
对于大多数基于表格构建解决方案的动态规划算法而言，时间复杂度通常取决于表大小以及填充每个单元格所需的时间。空间复杂度则主要由用于记录中间结果的数据结构决定。