按照字典序给出一系列的字符串，让你从中找出一个子序列，使得子序列中的第 i 个字符串可以通过增删改一个字符得到第 i + 1 个字符串，问你满足条件的最长子序列长度是多少。

就有点类似于最长上升子序列问题，区别在于这道题不是求递增，而是增删改一个字符后能否得到下一个字符串。

用最长上升子序列的做法， O(n^2)过了，这道题的另一个做法是构建无向图，求无向图的最长路径。

#include <bits/stdc++.h>
using namespace std;
const int N = 25005;
struct node {
  char name[20];
  int len;
} e[N];
int dp[N];
int main()
{
  int n = 0;
  while (~scanf("%s", e[n].name)) {
    e[n].len = strlen(e[n].name);
    n++;
  }
  int ans = 0;
  for (int i = 0; i < n; i++) {
    dp[i] = 1;
    for (int j = 0; j < i; j++) {
      int leni = e[i].len, lenj = e[j].len;
      if (leni == lenj) {
        int cnt = 0;
        for (int k = 0; k < leni; k++) {
          if (e[i].name[k] != e[j].name[k]) {
            cnt++;
          }
        }
        if (cnt == 1) {
          dp[i] = max(dp[i], dp[j] + 1);
        }
      } else if (leni == lenj + 1) {
        int cnt = 0;
        for (int l = 0, r = 0; l < leni; l++, r++) {
          if (e[i].name[l] != e[j].name[r]) {
            r--;
            cnt++;
          }
        }
        if (cnt == 1) {
          dp[i] = max(dp[i], dp[j] + 1);
        }
      } else if (lenj == leni + 1) {
        int cnt = 0;
        for (int l = 0, r = 0; l < lenj; l++, r++) {
          if (e[j].name[l] != e[i].name[r]) {
            r--;
            cnt++;
          }
        }
        if (cnt == 1) {
          dp[i] = max(dp[i], dp[j] + 1);
        }
      }
    }
    ans = max(ans, dp[i]);
  } 
  printf("%d\n", ans);
  return 0;
}