动态规划好难啊！！！
Sp6kw
·
2023-07-25 00:11:14
·
个人记录
动态规划
有好多人说：动态规划好难啊！！！！！今天我这个小小的蒟蒻试着来解决你们的疑问。
前言
之前我也被动态规划所困扰，非常理解你们的痛处。本文仅展示某些简单的例子，毕竟你们都有举一反三的能力，会了简单的，难的就会了，当然地慢慢来。你当然也可以狂虐100道简单DP（夸张的来说），然后去刷难一点的，你会发现没有那么难了。
如何写一个标准的DP
我们先看某GPT是如何来解决我们的烦恼的。
推导动态转移方程一般是针对具体的问题或算法进行的。
下面以动态规划问题为例，介绍推导动态转移方程的一般思路：
1. 定义状态：首先需要明确问题中涉及的变量和参数，将其抽象为状态。
状态可以是一维、二维甚至更高维的。
状态的选取应该满足以下两个条件：
包含问题的关键信息，满足无后效性。
2. 定义初始状态：确定初始状态的值，
通常是问题中的边界情况或已知条件。
3. 定义状态转移方程：根据问题的特性和状态之间的关系，
推导出状态转移方程。
动态转移方程描述了当前状态与之前状态之间的关系，
可以根据问题的特点进行推导。
4. 定义边界条件：确定状态转移过程中的边界条件，
包括初始状态和最终状态。
5. 设计动态规划算法：根据状态转移方程和边界条件，
设计动态规划算法，
通过迭代或递归的方式计算出最终的状态值或最优解。
需要注意的是，推导动态转移方程是一个思维活动，
需要对问题进行归纳总结和分析，
并根据问题的特点进行抽象和建模。
不同的问题可能需要采用不同的策略和方法来推导动态转移方程，
需要运用数学分析、逻辑推理和实际问题的理解等技巧。
以上是推导动态转移方程的一般思路，
具体的推导过程需要根据不同的问题而定。
啊？它在讲什么？
翻译一下：
首先，动态规划跟分治的某一个特点很像，都是将一个大问题拆成很多小问题，只不过它是使用地推解决的。
步骤：
明确你要求的东西。你连你在干什么都不知道你还写什么程序。
确定状态。将问题分成很多个阶段，并明确这个阶段的状态。然后用一个dp[i][j]...表示这个状态。这一步非常费脑子。你可能现在不懂什么是状态，看下面那个例子你就懂了。
状态转移方程。找出每个状态之间的关联，用一个状态转移方程表示出来。就是递推公式。
初始化。递推都得这么干。比如dp[0]=0;。这也很重要，因为它是问题的起点。
递推。无非就是将状态转移方程实现一下。（当然某些情况可以优化）
输出结果。通常是dp[n];或者dp[n][m];
上面这个仔细看，这有助于你写动态规划更轻松。
以0-1背包为例
我们需要解决的是如何在给定的一组物品中选择一些物品放入背包中，以使得它们的总价值最大，同时不能超过背包的容量。(weight是重量的意思，这里用它表示物体的大小）
让我们先定义一下状态。定义dp[i][j]为背包的容量为j时，前i个物品的最大价值。那么答案就是dp[n][m]了，即所有物品，容量为m时的最大价值。
状态转移方程也十分简单。先考虑使用dfs实现这道题，需要2种情况的扩展。一种是抛弃这一步的物品，另一种是选取物品，并将参数w加上这个物品的大小。说回dp就是说有两种方案。一个是dp[i-1][j]，即不选取第i个物品，最大价值与前i-1个物品的最大价值相同。另一个dp[i-1][j-weight[i]]+value[i]，j-weight[i]表示放入之后剩余的容量。
这里还要分2种情况。
一种是j 另一种就是j>=weight[i]，此时应在两种方案中选择较大的那一种。 那么如何初始化呢？首先创建一个dp[n+1][W+1](n是物品数量，W是背包容量)dp全都设置为0 _边界限制：第0个物品和当背包容量为0时，总价值肯定都是0，所以dp[i][0]=dp[0][j]=0。 来看一下伪代码 创建一个二维数组 dp[n+1][capacity+1]，用于存储子问题的最优解 // 初始化边界条件 对于所有的 i 从 0 到 n，dp[i][0] = 0 对于所有的 j 从 0 到 capacity，dp[0][j] = 0 // 填充表格 // 为了解决边界、越界等问题，j从1开始。 对于所有的 i 从 1 到 n： 对于所有的 j 从 1 到 capacity： 如果 weight[i-1] <= j: dp[i][j] = max(value[i] + dp[i-1][j-weight[i-1]], dp[i-1][j]) 否则: dp[i][j] = dp[i-1][j] 返回 dp[n][capacity] 题目： P1048 [NOIP2005 普及组] 采药 以硬币找零问题为例 问题：给定一定面额的硬币和一个要找零的金额，找出最少需要的硬币数量。 这该如何解呢？下面是详细分析。 题目在上面。 定义状态。题目求最少需要的硬币数量，可以将dp[i]定义为找零金额为i时最少的硬币数量。 先初始化数组。定义dp中的所有元素为无穷大，则dp[i]=无穷大时，表示找零金额为i时，不可能凑出此金额（个人的理解是无数个硬币也凑不了）。且dp[0]=0因为面额是0的时候不需要硬币。 动态转移方程。对于硬币的面值coin，如果coin\le i，那么coin可以使用。那么此时的硬币数量count=dp[i-coin]+1，i-coin表示当前找零金额-使用的硬币，那么dp[i-coin]表示{当前金额-硬币面值}这个金额需要的最少硬币数量。因为coin算一个新的硬币，所以要+1.所以动态转移方程为 dp[i] = \min_{j=0}^{n-1} \{ dp[i - coins[j]] +1\} 写程序，下面是伪代码 function coinChange(coins, amount): // 创建一个数组来保存最少需要的硬币数量 dp = new Array(amount + 1) dp[0] = 0 // 找零金额为0时不需要任何硬币 // 遍历从1到amount的所有金额 for i = 1 to amount: dp[i] = INFINITY // 初始化为无穷大，表示不可能达到的数量 // 针对每个硬币面额进行计算 for j = 0 to length(coins) - 1: if coins[j] <= i: count = dp[i - coins[j]] + 1 dp[i] = min(dp[i], count) // 返回最少需要的硬币数量 return dp[amount] 题目： P2834 纸币问题 3 以上都是非常简单的动态规划的例子。下面给出几道题，让你自己推导一遍过程，因为这些题都非常非常水，目的在于熟悉推导过程，锻炼思维。 题目： P1115 最大子段和 P1049 [NOIP2001 普及组] 装箱问题 P1616 疯狂的采药 无后效性 先来说一下无后效性这个东西。 在一个最优化问题中，如果一个给定问题的最优解包含了其他子问题的最优解，那么这些子问题的最优解也将是其自身子问题的最优解。 换句话说，当一个问题的最优解可以通过子问题的最优解来构造时，这个问题具有无后效性。 这意味着我们只需要关注当前问题的最优解，而 不需要考虑问题的求解历史或路径。 通过利用无后效性，我们可以将一个问题划分成多个子问题，并将子问题的最优解组合起来得到原问题的最优解。这种思想是动态规划算法的基础。 注意到了吗？上面哪些例子，都具有无后效性这个特点。 线性状态动态规划 故名思意，这种DP的状态空间具有线性结构。（大白话就是dp[n]这个数组是一维的） 上面的例子中，硬币找零问题就是线性状态dp。下面介绍一个更经典的线性状态动规。 P1020 [NOIP1999 普及组] 导弹拦截 这题不要太经典！ 这题能贪心，但是我们考虑动态规划解决： 题目。翻译成大白话就是求最长的单调不升子序列。 定义状态。题目要求最长的单调不升子序列，所以可以将dp[i]定义为选择第i个数时，最长的单调不升子序列的长度。 初始化。初始化为选择第i个数时的最坏情况，dp[i]=1所以将dp中的所有元素都赋值成1 考虑两种情况。第一种情况：这个数是这个单调不升子序列的第一个数，所以dp[i]=1.第二种情况：选择第i个数时，前面已经有j个数是这个单调不升子序列的一部分，由于单调不升，所以nums[j]\le nums[i]，需要枚举dp[j]的最大值。此时dp[i] = \max(dp[j]) + 1, \text{其中} 0 \leq j < i \text{且} nums[j] \le nums[i] 写程序。结合两种情况，最后输出dp[n]即可。下面是伪代码。 function longestNonIncreasingSubsequence(nums): n = length(nums) dp = new Array(n) // 创建一个长度为n的数组dp用于存储最长不上升子序列长度 dp[0] = 1 // 初始化dp数组的第一个元素为1 for i = 1 to n-1: dp[i] = 1 // 初始化dp数组的其他元素为1 for j = 0 to i-1: if nums[j] >= nums[i]: // 满足(不上升)条件 dp[i] = max(dp[i], dp[j] + 1) maxLen = max(dp) // 找到dp数组中的最大值，即最长不上升子序列的长度 return maxLen 可以看到，这种动态规划是比较简单的，因为它是线性的嘛，所以不用像太多复杂的东西。 总结 动规还是非常难的东西，这里讲的动规是非常非常简单的。总之本人juruo