0x00、引言假设有这么一道题：给定一串序列A={-2, 11, -4, 13, -5, -2}，要求求出 i 和 j ，使得Ai+......+Aj的和最大。这道题最直截了当的方法是暴力求解，从左端点到右端点依次遍历。但是这样时间复杂度会十分的高，这种问 ...

我们先看一个图片：这是一个经典问题，图片上的东东是"数塔"。第一层有一个数字，第二层有两个数字。。。以此类推。问题是，如果从第一层走到第n层（当然，不能走回头路），路径上的数字相加的最大和是多少呢？如果从上到下考虑，可能并不是特别好 ...

记忆化搜索，即在搜索过程中记录下搜索结果，在下次的搜索过程中如果算出过这个结果，就可以直接拿来用。举个栗子：现有一个问题，要求写出一个函数，功能是输出第n个斐波那契数列。斐波那契数列是这样的：1,1,2,3,5,8......直接的办法是开一个数 ...

0x00、Dijkstra并不是万能的前面我们讲过了Dijkstra算法，Dijkstra算法可以很好的解决边权均为正数的最短路径问题，但是，请看下图：（上面的点是A，左边的是B，右边的是C，作图的时候忘记打上去了TAT...）如果我们使用Dijkstra来解决从A走向，我 ...

0x00、复杂多条最短路径问题前面我们提到过多条最短路径类问题，诸如"新增边权"、"新增点权"、"求最短路径条数（新增计数器）"等类问题，这里面新增的内容被我们称为"第二标尺"。（传送门：多条最短路径情况）在多条最短路径类问题上，一般的出题 ...