DP——动态规划

动态规划算法

当涉及到解决具有重叠子问题的优化问题时，动态规划是一种常用的算法技术。它通过将问题分解为一系列重叠子问题，并使用递归或迭代的方式来解决这些子问题，最终得到问题的最优解。

动态规划的核心思想是将原始问题分解为更小的子问题，并通过解决这些子问题来构建原始问题的解。在解决子问题时，动态规划会将子问题的解保存起来，以便在需要时进行重复使用，从而避免了重复计算。

动态规划的一般步骤

要实现动态规划算法，可以按照以下步骤进行：

确定问题的状态：首先，需要确定问题的状态，这些状态应该能够唯一地表示问题的子问题。状态可以是一个或多个变量的组合，可以是一个数字、一个数组、一个矩阵等，具体取决于问题的性质。

• 定义状态转移方程：根据问题的定义和性质，确定问题的状态之间的转移关系，即如何从一个状态转移到另一个状态。这个方程通常是基于递推关系或者最优子结构性质来定义的。

• 确定初始条件：确定最小子问题的解，即初始状态的值。这些初始条件是问题的边界条件，用于开始递推计算。

• 确定计算顺序：确定计算子问题解的顺序，通常是从最小子问题开始，逐步计算更大的子问题，直到计算出原始问题的解。这个顺序可以是自顶向下的递归方式，也可以是自底向上的迭代方式。

• 计算最优解：根据状态转移方程和初始条件，计算出原始问题的最优解。可以使用递归或迭代的方式进行计算。

• 构建最优解：根据计算出的最优解和保存的中间结果，构建出原始问题的最优解。这一步通常是通过回溯或者追踪中间结果的方式进行。

需要注意的是，动态规划算法的实现可以使用递归或迭代的方式，具体取决于问题的性质和计算效率的要求。在实现过程中，可以使用数组、矩阵或者哈希表等数据结构来保存中间结果，以便在需要时进行查找和使用。

特殊DP——背包

背包问题是一个经典的优化问题，它可以通过动态规划算法进行求解。在背包问题中，有一个背包和一组物品，每个物品都有自己的重量和价值。目标是选择一些物品放入背包中，使得放入背包的物品总重量不超过背包的容量，同时使得放入背包的物品总价值最大化。

背包问题可以分为两种类型：0-1背包问题和无限背包问题。

0-1背包问题

每个物品只能选择放入背包一次或不放入。即物品的选择是一个二进制的决策。这种情况下，动态规划的状态可以定义为“在前i个物品中，背包容量为j时的最大价值”。状态转移方程可以表示为： dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]) 其中，dp[i][j]表示前i个物品中，背包容量为j时的最大价值，w[i]表示第i个物品的重量，v[i]表示第i个物品的价值。

完全背包问题

每个物品可以选择放入背包多次，即物品的选择是一个非负整数。这种情况下，动态规划的状态可以定义为“在前i个物品中，背包容量为j时的最大价值”。状态转移方程可以表示为： dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + v[i]) 其中，dp[i][j]表示前i个物品中，背包容量为j时的最大价值，w[i]表示第i个物品的重量，v[i]表示第i个物品的价值。

动态规划算法的实现步骤如下：

• 定义问题的状态：确定状态的定义，即dp数组的含义和维度。

• 初始化：根据问题的定义，初始化dp数组的初始值。

• 状态转移：根据状态转移方程，使用循环遍历物品和背包容量，更新dp数组的值。

• 返回结果：根据问题的定义，从dp数组中获取最优解的值。

• 可选的步骤：如果需要构建最优解的具体物品组合，可以使用额外的数据结构（如二维数组或哈希表）来保存选择的信息，然后根据这些信息构建最优解。

通过以上步骤，可以使用动态规划算法解决背包问题，并得到最优的物品选择方案和总价值。

总结

总结起来，实现动态规划算法的关键在于确定问题的状态和状态转移方程，并按照计算顺序进行递推或迭代计算，最终得到原始问题的最优解。