首先当 s 为回文字符串时，最少删除次数自然是1。

当 s 不为回文字符串时，这时就需要好好审题了，题目中对于【子序列】的定义是可以删除原字符串中的某些字符，那么对于任意长度的 s ，都可以通过删除所有 b，得到一个全是 a 的回文子序列。

那么 s 不为回文字符串时的最小删除次数就是2。

本道题主要考察以下两个知识点：

• 数组的基本操作。

• 多条件排序。

题目描述比较详细，仔细阅读即可得解。

本道题主要考察图论相关的知识，题目中要求解出邻居最少的城市，那么就需要求出一个城市最多可以到达几个城市，最终转化为求解各个城市之间最短距离的问题。

本道题中的城市图结构属于无向正权图，所以可以选择弗洛伊德算法（Floyd-Warshall），也可以选择迪杰斯特拉算法（Dijkstra）。

这里选择实现相对比较简单的弗洛伊德算法。

首先需要利用一个二维数组来记录各个顶点之间的距离：

然后需要对该数组进行 i 次更新，找出 [j, k] 是否存在一条从 [j, i] 到 [i, k] 的最短路径：

最后再筛选出邻居最少的城市：

解决本道题的重点在于理清楚 i 和 d 的关系。

第一种情况：i < d，无法制定工作计划，返回 -1。

第二种情况：i == d，只能每一天完成一项工作，那么最低难度为 i 项工作的难度之和。

第三种情况：i > d，以 i = [6，5，4，3，2，1]，d = 2 为例，一共有以下5种安排方式。

• [6]，[5, 4, 3, 1]

• [6, 5]，[4, 3, 2, 1]

• [6, 5, 4]，[3, 2, 1]

• [6, 5, 4, 3]，[2, 1]

• [6, 5, 4, 3, 2], [1]

那么对于任意 d 和 i （i > d），实际就是比较 d - 1 天的最小难度加上当前天的最大难度，一共有 i - d + 1 种可能（每天至少完成一项任务），那么递推公式为：

所以，本题是一道标准的动态规划题型，具体解题代码如下：