基础线性dp
钟昊原
一、dp的引入
动态规划（简称dp）是指把一个问题分解为若干个子问题，通过局部最优解得到全局最优的一种算法策略或者说一种思想方法。简单来讲，就是说用一个数组表示我们要求的问题的答案：如果你知道前一个问题的答案，你就可以推出后一个问题的答案。dp有以下几个常见的概念：
1.状态：指当前所考虑的子问题的情况。例如背包的已用体积、区间的起止点，以及用状态压缩手段压缩后的状态。
2.状态转移：指由前一个子问题的答案推出当前问题的答案。一般来讲会由一个表示赋值的等式给出，称为状态转移方程。
3.无后效性：指当前子问题的处理策略与后边问题的解答无关。要记住我们是从子问题的答案推出新问题的答案，与这个子问题答案怎么来的无关。
总的来讲，dp一般有以下三个步骤：
1.设计状态：指设计出合适的dp数组以及规定dp数组的含义。设计出的dp数组要能够形容各种状态并且能无后效性地在状态之间进行转移。
2.推理状态转移方程：顾名思义，关键在于如何从已知问题的答案推出当前问题的答案，有的时候需要多个方程，有的时候一个方程要包含多个子状态。
3.确定边界条件：递推的初值或者说记忆化搜索的回溯条件，以及各个数组的初值。
举个例子，以在学习递推时就学过的台阶问题为例，如果把这个当成dp：
问题：一个人走楼梯，一次可以跨一阶，可以跨两阶，求到达第n阶有多少种办法。
设计状态：dp[i]表示到达第i阶的方法数
状态转移：第i阶可以来自第(i-1)阶或第(i-2)阶，dp[i]=dp[i-1]+dp[i-2]
边界条件：到达第1阶只有一种办法，dp[0]=dp[1]=1
二、线性结构上的dp
线性dp往往指在一个序列上进行的dp，当然也可能有两个甚至多个序列。一般来讲，线性dp的三个步骤分别有以下特点：
设计状态：至少有一维表示当前考虑的对象在数列上的位置。
状态转移：必须找到这条线上前面的位置的dp值来推出当前位置的dp值。
边界条件：第一个位置单独讨论。
【例1 最大子段和】
给定一串数，求其中某一连续序列，使得这个序列中的数字之和最大，例如，5 -7 6 2 -5 -2 8 -3，要取到一段和最大的连续序列应该是“6 2 -5 -2 8”答案是9。
分析：按照三个步骤设计dp。首先是dp[i]的含义：如果它仅表示前i个数的子序列中最大子段和长度，那么在这个最大子段和不包含a[i]的情况下，dp[i+1]将无法由dp[i]得出。所以dp[i]的准确含义是“前i个数的子序列中，包含a[i]的子段，的最大和”。然后状态转移方程来自两个决策：既然a[i]一定要取，那么a[i]是继承dp[i-1]，还是自立门户？所以dp方程就是在两个决策中取max：dp[i]=max{dp[i-1]+a[i],a[i]}。最后注意边界条件是dp[1]=a[1]，这在写代码时不用特殊处理。最终答案为max{dp[i]}，时间复杂度为a[i]。
【例2 最长公共子序列（LCS）】
给两个子序列A和B，求长度最大的公共子序列。例如1 5 2 6 8 7和2 3 5 6 9 8 4 的最长公共子序列为 5 6 8（另一个解是2 6 8）。（如图）
A B C B D A B
B D C A B A
分析：设dp[i][j]为A1,A2,...,Ai和B1,B2,...,Bj的LCS长度，则当A[i]=B[j]时，dp[i][j]=dp[i-1][j-1]+1，否则dp[i][j]=max{dp[i-1][j],dp[i][j-1]}，时间复杂度为O(nm)。注意边界条件是所有的初始值为0，写代码时仍然不用专门处理。
【例3 最长不下降子序列（LIS）】
最长不下降子序列是一个不严格递增，允许不同位元素相等的序列。而它是子序列也表明它的长度一定小于等于原序列。且子序列在原序列的位置不一定连续。例如1 2 3 4 5 5是一个不下降序列，而1 3 2 2 5 5的最长不下降子序列就是1 2 2 5 5。
分析：这个序列的每一个数为止都有一个解, 作为子问题的解. 后面的问题的解就是从这些子问题的最优解继承过来的，所以设dp[i], 表示截止到Ai的解。
当下一个数要加入来的时候, 有两种情况
1.前面的数都比当前数更大, 因此以这个数为止的最长不下降子序列的长度就是1. 遍历到第一个数的情况也包含在内。
2.前面的数有不比当前数大的, 那么这个数的结果dp[i] = max(dp[i], dp[j] + 1). 这个过程遍历前面所有数的dp[j]进行比较。
最后的答案就是所有dp[i]里面的最大值。
【思考题 最长不下降公共子序列】
两个序列求公共子序列，但是这个子序列不仅要最长，还要满足它不严格单调。
提示：把例2和例3的dp结合起来，例2的解法为该题提供框架，例3的dp方程可以往例2的基础上添加一些条件。
三、背包问题
背包是动态规划的一个分支。总的来讲，背包问题可以描述为：给定一组物品，每种物品都有自己的重量w[i]和价格v[i]，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。这种问题的动态规划过程一般有以下特点：
状态设计：肯定有一维表示背包当前装入东西的总质量
状态转移：现在总质量为j的背包，装了质量为w[i]的物体之前的质量是j-w[i]，所以dp[j]要从dp[j-w[i]]来
边界条件：背包为空的时候价值是0（需要特别注意的一点是，千万不要用dp[w[i]]=v[i]来给dp数组赋初值，一定要用dp[0]=0。）
【例1 01背包】
有一个容量为 V 的背包，和一些物品。这些物品分别有两个属性，体积 w 和价值 v，每种物品只有一个。要求用这个背包装下价值尽可能多的物品，求该最大价值，背包可以不被装满。 在最优解中，每个物品只有两种可能的情况，即在背包中或者不在背包中（背包中的该物品数为0或1），因此称为0-1背包问题。
分析：对于每一个物品，有两种结果：能装下或者不能装下。第一，包的容量比物品体积小，装不下，这时的最大价值和前i-1个物品的最大价值是一样的。第二，还有足够的容量装下该物品，但是装了不一定大于当前相同体积的最优价值，所以要进行比较。由上述分析，子问题中物品数和背包容量都应当作为变量。因此子问题确定为背包容量为j时，求前i个物品所能达到最大价值。“状态”对应的“值”即为背包容量为j时，求前i个物品所能达到最大价值，设为dp[i][j]。初始时，dp[0][j](0<=j<=V)为0，没有物品也就没有价值。所以说dp方程是
j<w[i], dp[i][j]=dp[i-1][j] //背包装不下该物品，最大价值不变
j>=w[i], dp[i][j]=max{dp[i-1][j-w[i]]+v[i],dp[i-1][j]} //和不放入该物品时同样达到该体积的最大价值比较
但是空间复杂度能否优化？我们发现dp[i][j]的转移只与dp[i-1][j-w[i]]和dp[i-1][j]有关，即仅与二维数组本行的上一行有关。因此，我们可以将二维数组优化为一维数组。不过这里要注意两点：1.j<w的状态转移方程不再需要了。2.为保证每个物品只能使用一次，我们倒序遍历所有j的值，这样在更新dp[j]的时候，dp[j-w[i]]的值尚未被当前物品i修改，就不会出现一个物品重复使用的问题。此时的dp方程简化为
j>=w[i], dp[j]=max{dp[j-w[i]]+v[i],dp[j]}
【例2 完全背包】
与01背包不同的是，完全背包每个物品可以使用多次，或者也可以理解为每个物品的数量有无穷多个。
分析：在讲解01背包的优化时我们提到“为保证每个物品只能使用一次，我们倒序遍历所有j的值”。那如果正序遍历，更新dp[j]的时候，dp[j-w[i]]的值已经被i修改，i就可以重复使用了。
（思考）在前两个模板的基础上，如果限制条件不止一个（例如同时限制体积和质量），应该如何解决？如果收益有A、B两种，要求保证A最大的前提下B尽可能大，应该如何解决？
【例3 金明的预算方案】
在01背包的基础上，将物品分为两种：主件与附件，附件是从属于某个主件的，如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有 0 个、1 个或 2 个附件。
分析：先考虑1个附件的情况。对于有1个附件的主件而言，有3种选择方式：1.什么都不选；2.只选主件；3.全部选上。而我们可以把这三种情况拆成2个不同的物品，即“纯主件”和“主件+附件”。那么2个附件同理，拆成4个物品：“纯主件”、“主件+附件A”、“主件+附件B”、“主件+附件A+附件B”。然后执行普通的01背包就好了。
【思考题 分组背包】
物品大致可分为 k 组，每组中的物品相互冲突，最大的价值是多少。
原文：https://www.cnblogs.com/chyuhoinACM/p/15017522.html