前置知识 字典树 Trie Trie 是一种能够快速插入和查询字符串的多叉树结构。节点的编号各不相同，根节点编号为0，其他节点用来标识路径还可以标记单词插入的次数。边表示字符。 支持操作 Trie 维护字符串的集合，支持两种操作： 向集合中插入一个字符串：void insert(char *s) 在…

1. 邻接矩阵 思想： 利用二维数组 g[N][N] 存储所有的点到点的权值。 其中 N 为点的数量，g[i][j] 表示点 i 到点 j 的权值。 时间复杂度：$\mathcal{O}(n^2)$ 空间复杂度：$\mathcal{O}(n^2)$ 应用： 只在点数不多的稠密图使用。 大部分情况下点…

1. 数字三角形模型 1.1 模板题 898. 数字三角形 原题链接 描述 给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 …

1. 01背包问题 1.1 模板题 01背包问题 原题链接 描述 有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。 第 i 件物品的体积是 vi，价值是 wi。 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。 输出最大价值。 输入格式 第一行两个整数，N，V…