最长上升子序列

1、最长上升子序列(easy)：给定一个长度为 $n$ 的数组 $a$ ($n \leq 1000$)，求其最长上升子序列(非降)的长度。注意：子序列不一定是连续的
2、对于线性 DP，通常用 $dp[i]$ 表示以 $i$ 结尾或到 $i$ 为止，如果有对应的代价，通常用 $dp[i][j]$ 表示到 $i$ 为止花费 $j$ 的代价的价值最值(见背包问题)
3、确定状态：令 $dp[i]$ 表示以 $i$ 结尾的最长上升子序列长度
4、确定转移：对于输入的每一个 $a[i]$ ，可知都有两种情况：一种是它作为最长上升子序列的起点，另一种是它接续在其他上升子序列之后。对于 $a[i]$ 作为起点，$dp[i] = 1$ ；对于 $a[i]$ 作为接续，应向左搜寻一个 $j \lt i$，$dp[i] = max(dp[i], dp[j] + 1)$ ，遍历取最大值。总结状态转移方程为：
$$ \left\{ \begin{array}{l} dp[i] = 1 &作为起点 \\\\ dp[i] = max(dp[i], dp[j] + 1) &作为接续 \\\end{array} \right. $$
5、易知，该算法复杂度为 $O(n^2)$，只能处理小规模数据，仍需优化

采药

1、采药：输入 $T$ 和 $M$ 分别表示拥有的总时间和药材种类($T \leq 1000, M \leq 100$)，对于每种药材，输入 $t_i$ 和 $v_i$ ($t_i,v_i \leq 100$)，表示采摘该药材需要的时间和药材的价值，每种药材只可采摘一次。可能输入多组数据，直到 $T$ 和 $M$ 都为 $0$ 结束。对于每组数据，输出其规定时间内能采摘的药材价值之和的最大值
2、对于每种药材都可以用 $0$ 或 $1$ 标记状态(是否被选择)，是一个01 背包问题。运用动态规划的思想，先确定状态：令 $dp[i][j]$ 表示到第 $i$ 个物品为止，用了 $j$ 的时间，所获得的最大价值
3、再确定转移，对于当前的 $dp[i][j]$ ，有两种情况：如果没选择当前第 $i$ 个物品，则 $dp[i][j] = dp[i-1][j]$ (没有花费时间，没有增加价值，和上一个——到第 $i-1$ 个物品的状态相同)；如果选择了当前第 $i$ 个物品，则 $dp[i][j] = dp[i-1][j-t[i]] + v[i]$(当前状态等同于 $dp[i-1][j-t[i]]$ 上一个物品的价值 + 当前物品价值，其中因为当前 $dp[i][j]$ 花费的总时间为 $j$，所以上一个物品的时间应为 $j-t[i]$)。总结状态转移方程为：
$$dp[i][j] = \left\{ \begin{array}{l} dp[i-1][j]&,没选择当前物品 \\ \\ dp[i-1][j-t[i]] + v[i]&,选择了当前物品 \\ \end{array} \right. $$
4、最后确定初始化和边界：初始化 $dp[0][i] = 0$(到第 $0$ 个物品无论花费多少时间，价值为 $0$)；边界为 $i \leq M, j \leq T$

递推求组合数

1、组合数中有 $C_n^m = C_{n-1}^{m-1} + C_{n-1}^m$ 。其中 $C_n^m$ 意为从 $n$ 个元素中选出 $m$ 个元素有多少种不同组合，其总的可能可划分为组合中选了第一个和组合中没选第一个两种。如果组合中选了第一个，那么剩下的方案数还有 $C_{n-1}^{m-1}$ 种(从剩余元素中选 $m-1$ 个)；如果组合中没选第一个，那么剩下的组合中还有 $C_{n-1}^m$ 种；这两种结果互斥，因此相加便可得到总的方案
2、这种方法运用了递推与DP的思想，上面的等式为状态转移方程。其中，$C_n^m$ 为新状态，通过方程将其转移为两个老状态的和。此外，需要确定起始点和边界：起始点为 $C_i^0 = 1$ (从任意多的元素中选 $0$ 个，有 $1$ 种方案——不选)；边界为 $C_i^j$ (其中 $0 \leq j \leq i$，$i \leq n$)

生成树 与 MST

1、在无向连通图中，找出一个节点最多的子连通图(有 $n$ 个点，$n-1$ 条边)，这样的子连通图一定是树，称为生成树。最小生成树指各边权值之和最小的生成树，称为 MST(Minimum Spanning Tree)
2、如下图，便是一幅无向连通图，该图的最小生成树为图中红色所示的子连通图(有 $5$ 个点，$4$ 条边)，其权值和为 $10$
3、对于最小生成树的生成，可以通过基于点的 Prim 最小生成树与基于边的 Kruskal 最小生成树完成