关于动态规划的一些想法

     动态规划的核心思想是避免重复计算，以空间换时间

     动态规划中最优子结构的两个要点：1.怎么存储算法过程中产生的子解空间；2.状态转移方程：计算包含新元素的解的解空间

    举例说明：双调巡游

     对于要点1：

        双调巡游中的解空间具有对称性：两个车途径的点互换，距离结果不变，计算时可以做为同一解（如果考虑时间，车速则不能为同一解）

        所以考虑是否可以只保存上一个计算的途径点A的信息，假设只保存上一个途径点的信息做为解空间的入口，下一个计算的途径点B计算时需要计算选中的车最后一个途径点C到B的距离，那么该途径点的解空间中应该包含A，则计算A时，需要修改另一个车中目前所有解空间中的解，使其成为包含A的解，而修改解则是该解中第一个车中最后一个途径点D到A的值，但是解中并没有保存这个信息

       所以解中并不能只包含上一个计算的途径点A的信息，需要保存两个车辆的途径点C、D信息，那么是否可以只保存两个车辆的最后一个途径点信息呢，前面分析过程中，我们都确实只关注了车辆的最后一个途径点，说明是可行的，有一点需要注意，两个车的最后一个途径点必然有一个是上一个途径点，又根据对称性，解空间包含上一个途径点以及从第一个途径点到上上一个途径点的解

    对于要点2：

      正如前面分析过程，我们确定下一个途径点B的解时，是上一个目标解空间中的任意一个解中的两个车中的任一一个车的最后一个途径点C、D到正在计算的途径点B的距离值

代码如下：

public static double curiseForTSPSolution(List<Location> locations) {
        locations = CollectionsTool.sortLocationBySmx(locations);

        int length = locations.size();
        double[][] totalDistance = new double[length][length];
        double[][] distances = new double[length][length];
        for (int i = 1; i < length; i++) {
            for (int j = 0; j < i; j++) {
                double distance = LineSegmentTool.calcualtionDistance(locations.get(i), locations.get(j));
                distances[j][i] = distance;
            }
        }

        for (int i = 1; i < length; i++) {
            for (int j = 0; j < i - 1; j++) {
                //车的最后一个途径点为其他途径点
                double other = totalDistance[i - 1][j] + distances[j][i];
                totalDistance[i][i - 1] = other;
                //车的最后一个途径点为上一次计算的途径点
                double preLast = totalDistance[i - 1][j] + distances[i - 1][i];
                totalDistance[i][j] = preLast;
            }
        }

        double minDistance = totalDistance[length][0];
        for (int i = 0; i < totalDistance[length].length; i++) {
            double distance = totalDistance[length][i];
            if (minDistance > distance) {
                minDistance = distance;
            }
        }
        return minDistance;
    }