1.线性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值。
边界条件：第一个位置单独讨论。
微信打赏