算法专题1——动态规划 Dynamic Programming，DP

零

DP学一次忘一次，干脆写个总结以后好复习

原文发布时间：2022-09-29 16:47:04
本文主要为，代码随想录的学习笔记

质量分太低，进行扩展补充

原文

一、What

如果某⼀问题有很多重叠⼦问题，使⽤动态规划
是最有效的。
由dp[j-weight[i]]推导出来的，然后取max(dp[j], dp[j - weight[i]] + value[i])。
所以动态规划中每⼀个状态⼀定是由上一个状态推导出来的

区分于贪心
贪心没有状态推导，⽽是从局部直接选最优的

二、解题步骤

1. 确定dp数组（dp table）以及下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序
5. 举例推导dp数组

三、如何debug

打印dp数组
写代码前将状态转移在dp数组上具体模拟一遍，确认是想要的结果

这道题目我举例推导状态转移公式了么？
我打印dp数组的日志了么？
打印出来了dp数组和我想的⼀样么？

完善补充

探秘DP算法的工作原理

动态规划（Dynamic Programming）是一种强大的算法技术，用于解决各种计算问题，包括优化、最短路径、序列匹配、资源分配等等。本文将深入探讨动态规划算法的工作原理，以及它在解决各种问题中的应用。

什么是动态规划？

动态规划是一种通过将问题分解为子问题并将它们的解决方案存储在表格中以避免重复计算的算法技术。它通常适用于满足以下两个条件的问题：

1. 最优子结构：问题的最优解可以通过子问题的最优解来构建。
2. 重叠子问题：问题可以分解为多个重叠的子问题，这些子问题可以在不同上下文中多次出现。

动态规划通过解决子问题来构建整个问题的解，从而避免了不必要的重复计算，提高了算法的效率。

动态规划的基本原理

动态规划算法通常遵循以下基本原理：

1. 问题拆分：将原始问题分解为一系列子问题，这些子问题通常是相互重叠的。
2. 状态定义：明确定义每个子问题的状态。状态是问题的一个关键属性，用于描述问题的某一方面。
3. 状态转移方程：确定如何从一个状态转移到另一个状态。这通常是问题的核心部分，定义了问题的解决方案。
4. 初始化：设置初始状态的值，通常是最简单的情况的解。
5. 自底向上求解：使用状态转移方程自底向上地求解子问题，直到解决了整个问题。

动态规划的经典问题

动态规划算法广泛应用于各种问题，以下是一些经典的示例：

1. 斐波那契数列：通过动态规划可以高效地计算斐波那契数列的第n项，而不需要递归。
2. 最长公共子序列：用于比较两个字符串，找到它们的最长公共子序列。
3. 最短路径问题：例如，Dijkstra算法和Floyd-Warshall算法可以使用动态规划来解决最短路径问题。
4. 背包问题：用于在给定容量的情况下，选择一组物品以最大化其价值，而不超过容量。
5. 编辑距离：用于计算将一个字符串转换为另一个字符串所需的最少编辑操作数。

动态规划的优缺点

动态规划算法的优点包括：

• 高效性：通过避免重复计算，可以显著提高问题的解决效率。
• 通用性：适用于解决各种问题，从计算问题到优化问题。

然而，动态规划算法也有一些缺点：

• 需要额外的内存：为了存储子问题的解，需要额外的内存空间。
• 需要定义状态和状态转移方程：有时难以确定问题的状态和状态转移方程。

代码案例

注意：动态规划的实现方式会因问题而异，但通常都包括问题的拆分、状态定义、状态转移方程、初始化等步骤。

案例1：斐波那契数列

动态规划问题的具体实现代码会根据不同的问题而异。以下是一个经典的动态规划问题示例——斐波那契数列的Python代码：

def fibonacci(n):
    fib = [0] * (n + 1)
    fib[0] = 0
    fib[1] = 1

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

    return fib[n]

n = 10
result = fibonacci(n)
print(f"The {n}-th Fibonacci number is {result}")

这个代码用动态规划来计算斐波那契数列的第n个数，避免了递归的重复计算。

案例2：0/1背包问题

理解动态规划的概念和应用需要逐渐深入，因此我们将探讨一个稍微复杂一点的问题：0/1背包问题（0/1 Knapsack Problem）。
这是一个经典的动态规划问题，涉及如何在给定容量的情况下选择一组物品，以最大化它们的总价值，同时保持总重量不超过容量。

以下是一个Python示例代码，解决0/1背包问题：

def knapsack(values, weights, capacity):
    n = len(values)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(n + 1):
        for w in range(capacity + 1):
            if i == 0 or w == 0:
                dp[i][w] = 0
            elif 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][capacity]

# 示例
values = [60, 100, 120]
weights = [10, 20, 30]
capacity = 50
result = knapsack(values, weights, capacity)
print(f"最大总价值为 {result}")

上述代码使用动态规划来解决0/1背包问题。knapsack函数接受物品的价值列表values、物品的重量列表weights以及背包的容量capacity作为输入，返回最大总价值。它使用二维数组dp来保存子问题的解决方案，然后通过填充表格中的值来逐步计算出最优解。

这个示例展示了如何使用动态规划来解决更复杂的问题，动态规划的核心思想是将问题分解为子问题，通过解决子问题来构建最终的解决方案。

希望这个示例能帮助更好地理解动态规划的实际应用。

案例3：最长递增子序列问题

当涉及更复杂的动态规划问题时，问题的实现会更加复杂。以下是一个稍复杂的示例：最长递增子序列（Longest Increasing Subsequence, LIS）。
这个问题的目标是：找到给定序列中的最长递增子序列。

下面是一个用Python解决LIS问题的示例代码：

def longest_increasing_subsequence(arr):
    n = len(arr)
    lis = [1] * n

    for i in range(1, n):
        for j in range(0, i):
            if arr[i] > arr[j] and lis[i] < lis[j] + 1:
                lis[i] = lis[j] + 1

    max_length = max(lis)
    return max_length

# 示例
sequence = [10, 22, 9, 33, 21, 50, 41, 60, 80]
result = longest_increasing_subsequence(sequence)
print(f"最长递增子序列的长度为 {result}")

longest_increasing_subsequence函数接受一个整数序列作为输入，并返回最长递增子序列的长度。它使用一个列表lis来跟踪每个元素的LIS长度，然后通过填充表格中的值来计算最长递增子序列的长度。

这是一个相对较复杂的动态规划问题，需要利用子问题的解构建最终的解。动态规划的复杂性通常随着问题的难度而增加。

结语

动态规划是一种强大的算法技术，可以应用于各种计算问题。
了解动态规划的基本原理和应用领域可以帮助您更好地解决复杂的问题，提高算法的效率。
希望这篇文章能帮助您更好地理解和应用动态规划算法。