动态规划基础

5.1 动态规划的定义。

动态规划（Dynamic Programming，DP） 是一种优化方法，用于通过将复杂问题分解为更简单的子问题来解决复杂问题。动态规划 有效地用于可以分解为重叠子问题并具有最优子结构的任务。

工作原理：

1. 最优子结构：

如果一个问题的最优解可以由其子问题的最优解构建，则该问题具有最优子结构。这意味着可以通过解决几个较小的子问题来解决更大的问题。

2. 重叠子问题：

如果问题的子问题在解决过程中重复多次，则该问题具有重叠子问题。动态规划 通过记忆已解决的子问题的结果（记忆化）来有效解决具有重叠子问题的任务。

3. 记忆化和表格化：

记忆化（自顶向下）：递归方法，将子问题的结果保存在内存中以避免重复计算。

表格化（自底向上）：迭代方法，子问题的结果被计算并保存在表格（通常是数组）中，用于计算最终结果。

动态规划问题示例

5.2 背包问题。

问题:

有一组物品，每个物品都有重量和价值。需要选择某些物品放入一个容量有限的背包中，以最大化总价值。

重要！ 不同于易于用贪心算法解决的类似问题，这个问题中的物品不能被分割。

解决方案:

创建一个表格，行对应物品，列对应背包的可能容量。单元格中的值表示给定数量物品和容量的最大价值。

时间复杂度: O(n * W)，其中 n 是物品数量，W 是背包容量。

Python代码示例：

def knapsack(weights, values, W):
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
            
    for i in range(1, n + 1):
        for w in range(W + 1):
            if weights[i - 1] <= w:
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])
            else:
                dp[i][w] = dp[i - 1][w]
            
    return dp[n][W]
        
        

5.3 最短路径问题

问题:

寻找加权图中所有顶点对之间的最短路径。

解决方案:

使用一个表格，行和列对应图中的顶点。单元格中的值表示两顶点间的最短距离。

时间复杂度: O(V^3)，其中 V 是顶点数量

Python代码示例：

def floyd_warshall(graph):
    v = len(graph)
    dist = list(map(lambda i: list(map(lambda j: j, i)), graph))
            
    for k in range(v):
        for i in range(v):
            for j in range(v):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
            
    return dist
        
        

5.4 动态规划与其他方法的比较。

与暴力法（brute force）的比较：

时间复杂度：

• 暴力法：通常具有指数级时间复杂度（例如，费波那契数列问题的O(2^n)）。
• 动态规划：将时间复杂度降低到多项式级（例如，费波那契数列问题的O(n)）。

空间复杂度：

• 暴力法：可能使用较少内存，但时间消耗高。
• 动态规划：可能使用更多内存来存储中间结果（例如，带有记忆化的费波那契数列问题的O(n)），但节省了时间。

与贪心算法（greedy algorithms）的比较：

最优性：

• 贪心算法：不总是能找到全局最优解，但执行速度更快，且实现简单。
• 动态规划：找到全局最优解，但需要更多的计算资源。

问题示例：

• 贪心算法：分数背包问题，最小生成树（MST）。
• 动态规划：整数背包问题，最长公共子序列（LCS）。