题目记不清楚了，大概就是：
给一个字符数组chars，有诸多字符；再给一个字符串str以及一个起始光标位置start。从左到右查询str中字符在chars中的位置，并移动光标，问最少移动的步数。tips：chars中字符会重复，str中的字符也会重复。
-
第一反应就是一个分叉树方式的执行流程：
因此给出的答案是递归回溯，A了70%，无论如何想不出优化方式 ...
事后仔细想了一下，发现问题在于，从str的一个字符a到下一个字符m，假设chars中有3个a，3个m，那么按照递归的处理方式，最终会出现9条分支。但实际上，有可能成为下一次运算的潜在最小路径只有3条，3个a分别到第一个m的路径，其中最小的一条作为潜在路径；3个a分别到第二个m的路径，其中最小的一条作为潜在路径；3个a分别到第三个m的路径，其中最小的一条作为潜在路径。
那有人说，剪枝不就好了。这恰恰是递归解决不了的问题。
递归+回溯的思想有两个：深度遍历 or 广度遍历。深度遍历是1对1，广度遍历是多对1。
动态规划的思想是：多对1，或者1对多（就是多对多），每次刷新一层，而不是一个。
说的模糊了，这里给个简单的示意图（个人理解，觉得不正确的望指出）
这里红线代表一层，圆圈是红线上的节点。从递归角度考虑，从上一层到下一层，如果是深度遍历，就是 1 > return > 2 > return > 3 > return > 4 > return 5 > return 6 > return。如果是广度遍历，就是 1 > 4 > return > 2 > 5 > return > 3 > 6 > return。这题需要的是 1，2，3 return；4，5，6 return。这是动态规划能做到而递归做不到的（递归也可以采用第一种方式：1 > return > 2 > return > 3 > return > 4 > return 5 > return 6 > return），带来的就是时间复杂度提高。
解法 -- 递归回溯
每一层都要比上一层多算maxListSize次，最后一层要执行maxListSize ^ str.length()次。最大时间复杂度O(maxListSize ^ str.length())，maxListSize是str的所有字符中，在chars中出现次数最多的字符的出现次数。
public static int min = Integer.MAX_VALUE;
public static void recursive(char[] strToChar, int i, int start, int curStep, int cLen, HashMap<Character, List<Integer>> map) {
if (i == strToChar.length) { // 停止递归的条件
min = Math.min(min, curStep);
return;
}
char c = strToChar[i];
// 若和前一个元素一样,则只要0步,i+1,其他不变 (多A了5%)
if (i > 0 && c == strToChar[i - 1]) {
recursive(strToChar, i + 1, start, curStep, cLen, map);
return;
}
List<Integer> list = map.get(c);
for (int end : list) {
int t = Math.abs(end - start);
int nextStep = Math.min(t, cLen - t);
recursive(strToChar, i + 1, end, curStep + nextStep, cLen, map);
}
}
// 获取元素数组的元素与对应位置
public static HashMap<Character, List<Integer>> getMap(String chars) {
int length = chars.length();
HashMap<Character, List<Integer>> map = new HashMap<>(26);
for (int i = 0; i < length; i++) {
char c = chars.charAt(i);
if (map.containsKey(c)) {
List<Integer> li = map.get(c);
li.add(i);
// 获取map中list的最长的长度
maxListSize = Math.max(maxListSize, li.size());
} else {
List<Integer> list = new ArrayList<>(128);
list.add(i);
map.put(c, list);
}
}
return map;
}
解法 -- 动态规划
最大时间复杂度O(str.length() * maxListSize * maxListSize)，maxListSize是str的所有字符中，在chars中出现次数最多的字符的出现次数。
public static int maxListSize = 1;
public static int min = Integer.MAX_VALUE;
public static int dpSolution(char[] strToChar, int start, int cLen, HashMap<Character, List<Integer>> map) {
// a有2个,b有3个,从a->b的最小值只用计算3种,不用全部保留; 最后一位记录当前start
// [0][x]记录当前步数; [1][x]记录当前start
int[][] dp_ = new int[2][maxListSize + 1]; // 副本
int[][] dp = new int[2][maxListSize + 1];
char c = strToChar[0];
List<Integer> list = map.get(c);
int preLen = list.size();
for (int i = 0; i < preLen; i++) {
int t = Math.abs(list.get(i) - start);
int nextStep = Math.min(t, cLen - t);
dp_[0][i] = nextStep; // start到当前位置需要多少步
dp_[1][i] = list.get(i); // 记录当前位置
dp[0][i] = nextStep; // start到当前位置需要多少步
dp[1][i] = list.get(i); // 记录当前位置
}
for (int i = 1; i < strToChar.length; i++) {
c = strToChar[i];
list = map.get(c);
for (int j = 0; j < list.size(); j++) {
int curEnd = list.get(j);
int minCurStep = Integer.MAX_VALUE;
for (int k = 0; k < preLen; k++) { //preLen不可能为0,因此minCurStep必被刷新
int t = Math.abs(curEnd - dp[1][k]);
int nextStep = Math.min(t, cLen - t);
minCurStep = Math.min(minCurStep, nextStep + dp[0][k]);
}
// 将下一轮结果保存到副本中
dp_[0][j] = minCurStep;
dp_[1][j] = curEnd;
}
// 更新preLen
preLen = list.size();
// 刷新副本到主dp中
for (int[] ele : dp_) {
System.arraycopy(dp_[0], 0, dp[0], 0, ele.length);
System.arraycopy(dp_[1], 0, dp[1], 0, ele.length);
}
}
for (int i = 0; i < preLen; i++) {
min = Math.min(min, dp[0][i]);
}
return min;
}
时间检验
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
String chars = sc.nextLine();
String str = sc.nextLine();
int start = sc.nextInt();
if ("".equals(str)) {
System.out.println(0);
return;
}
HashMap<Character, List<Integer>> map = getMap(chars);
long t1 = System.nanoTime(), t2;
// 递归
recursive(str.toCharArray(), 0, start, 0, chars.length(), map);
int resR = min;
System.out.println(((t2 = System.nanoTime()) - t1) / 1000 + " ms");
// 动态规划
min = Integer.MAX_VALUE;
int res = dpSolution(str.toCharArray(), start, chars.length(), map);
System.out.println((System.nanoTime() - t2) / 1000 + " ms");
if (resR != res) {
throw new Exception("dp error");
}
System.out.println(min);
}
// 输出
asdfasdfmasdoifaosdfhaosdmfoaierafasdfrtrenbvmbpodfgjdsfnvxcnviofdtuweortufasbdcnxmcvnjksdfhgoeritfsdfjknskadfhjadsnmopireawrffdjasdfabdfuioasdfjasdlfaldfopikmovndifujghbvqwerrtyuioplkjhmnbvgfdcsxzayh
yhnbgtamo
0
63471 ms
178 ms
82
Process finished with exit code 0
可以看到，chars仅仅是200个字符，时间就差300多倍。
