学习动态规划中更多常用的DP,如线性DP、区间DP、树形DP、存在DP、计数DP、数位DP、状压DP、概率DP

线性 DP-最长上升子序列


  • 最长上升子序列

    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)$,只能处理小规模数据,仍需优化

阅读更多
C++DP动态规划

学习动态规划中典型的背包问题,通过动态规划的思想不重不漏地表达整个集合,推导出线性的状态转移方程

01 背包-采药


  • 采药

    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$

阅读更多
C++背包问题动态规划

学习通过递推法或公式法求组合数 C(n, m)

递推求组合数


  • 递推求组合数

    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$)

阅读更多
C++数学组合数

学习基于点的 Prim 最小生成树和基于边的 Kruskal 最小生成树

Prim 最小生成树(朴素)


  • 生成树 与 MST

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

阅读更多
C++PrimKruskal