华为OD机试之找出经过特定点的路径长度（Java源码）

找出经过特定点的路径长度

题目描述

输入描述

输出描述

用例

源码和解析
解析：

因此可以使用动态规划算法进行求解，不懂的可以到我的个人主页去算法专栏查找。
示例代码：

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class T42 {
	static int num[] = null;// 记录 每次dfs产生的 临时数据
	static String objInput = "";
	static int min = -1;// 最小路径距离
	static Map<Character, List<Integer>> map = null;

	public static void main(String[] args) {
		String input = "ANTBSEDXQOKPUAVGIFWHJLYMCRZB";
		objInput = "ABCB";
		map = new HashMap<Character, List<Integer>>();
		for (int i = 0; i < objInput.length(); i++) {
			if (!map.containsKey(objInput.charAt(i))) {
				map.put(objInput.charAt(i), new ArrayList<Integer>());
			}
			for (int j = 0; j < input.length(); j++) {
				if (input.charAt(j) == objInput.charAt(i)) {
					if (map.get(input.charAt(j)).contains(j))
						continue;
					map.get(input.charAt(j)).add(j);
				}
			}
		}
		System.out.println(map);
		num = new int[objInput.length()];
		dfs(0);
		System.out.println(min);
	}

	/**
	 * 
	 * @param p
	 *            位置序号 从0开始 通过该序号 可以取到键及其对应的列表
	 */
	public static void dfs(int p) {
		if (p >= objInput.length()) {
			int tempDistance = num[0];//
			// System.out.print(num[0]+" ");
			for (int i = 1; i < num.length; i++) {
				tempDistance += Math.abs(num[i] - num[i - 1]);
				// System.out.print(num[i]+" ");
			}
			// System.out.println();
			if (min == -1) {
				min = tempDistance;
			}
			if (tempDistance < min) {
				min = tempDistance;
			}
			return;
		}
		for (int i = 0; p < num.length
				&& i < map.get(objInput.charAt(p)).size(); i++) {
			num[p] = map.get(objInput.charAt(p)).get(i);
			dfs(p + 1);
		}

	}

}

代码运行示意图：