动态规划——总结

先把前面介绍的动态规划模型列举如下：

（1）最大连续子序列和

令 dp[i]表示以 A[i]作为结尾的连续序列的最大和。

（2）最长不下降子序列（LIS）

令 dp[i]表示以 A[i]作为结尾的最长不下降子序列长度。

（3）最长公共子序列（LCS）

令 dp[i][j] 表示字符串 A的 i号位和字符串 B的 j号位之间的 LCS长度。

（4）最长回文子串

令 dp[i][j] 表示 S[i]至 S[j]所表示的子串是否是回文子串。

（5）数塔 DP

令 dp[i][j] 表示从第 i行第 j个数字出发的到达最底层的所有路径上所能得到的最大和。

（6）DAG最长路

令 dp[i]表示从 i号顶点出发能获得的最长路径长度。

（7）01背包

令 dp[i][v]表示前 i件物品恰好装入容量为 v的背包中能获得的最大价值。

（8）完全背包

令 dp[i][v]表示前 i件物品恰好放入容量为 v的背包中能获得的最大价值。

特别说明：一般来说，“子序列”可以不连续，“子串”必须连续。

先看（1）~（4），可得到当题目与序列或字符串（记为 A）有关时，可以考虑把状态设计成下面两种形式，然后根据端点特点去考虑状态转移方程。

1. 1. 令 dp[i]表示以 A[i]结尾（或开头）的 XXX。
   2. 令 dp[i][j]表示 A[i]至 A[j]区间的 XXX。

其中 XXX均为原问题的表述。

接着看（5）~（8），这类题目需要分析题目中的状态需要几维来表示，然后对其中的每一维采取下面的某一个表述：

1. 1. 恰好为 i。
   2. 前 i。

在每一维的含义设置完毕之后，dp数组的含义就可以设置成“令 dp数组表示恰好为 i （或前 i）、恰好为j（或前 j）……的 XXX”，其中 XXX为原问题的描述。接下来就可以通过端点的特点去考虑状态转移方程。