Best Meeting Point

  • Hard
  • keyword: 数学, DP
  • 类似: post office, gas station, btbss, copy book

A group of two or more people wants to meet and minimize the total travel distance. You are given a 2D grid of values 0 or 1, where each 1 marks the home of someone in the group. The distance is calculated using Manhattan Distance, where distance: $$(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|$$

  • For example, given three people living at (0,0), (0,4), and (2,2):
    1 - 0 - 0 - 0 - 1
|   |   |   |   |
0 - 0 - 0 - 0 - 0
|   |   |   |   |
0 - 0 - 1 - 0 - 0

思路1: 动态规划

  • 一看到这种选择到固定点的最小距离和, 就想到区间动态规划: post office. 因为这个是求: min/max/count中的min嘛.

  • 那么DP的公式是什么呢?

    • 可以看到: 每一个位置到达所有点的Manhattan distance就是绝对值的纵横坐标差. 所以可以分成2部分看. 以下图举例, 一开始的位置在A, 那么meeting point可以向右, 即B, 或者向下, 即C.
      1 - 0 - 0 - 0 - 1
|   |   |   |   |
0 - A - B - 0 - 1
|   |   |   |   |
0 - C - 1 - 0 - 0
    • 可以看到公式: $$F[B] = F[A]+1-1-1-1$$, $$F[C] = F[A]+1+1+1-1$$. 这是因为向右平移, 那么左侧的1都会在dx上面+1, 而dy不变, 同时右侧的1都会在dx上面-1. 同理, 向下平移的话, 上面的ones会+1, 下面的ones会-1. 注意: 同一行的ones也会导致dy+1.

  • 代码怎么写呢?

思路2: 数学规律

  • 这里先有个定理要知道: 到达所有点的最小距离差是这些点的median. 参考stackexchange的证明.
  • 有因为Manhattan distance是2部分, 所以分别计算所有1在横轴/纵轴的映射. 注意: 有多少个1就要记录几次, 并不能因为映射相同就忽略, 因为距离都是要算的.
  • 所以上图在y的映射是: {0,0,1,2}, 在x的映射是: {0,2,4,4}. 然后怎么计算geometry median呢?
  • 计算geometry median: {0,0,1,2,5} => median是1, 所以距离和是: $$|0-1| + |0-1| + |1-1| + |2-1| + |5-1| = 7$$. 也可以这样看: sum = (5-0)+(2-0) = 7. (注意1就不用处理了)
  • 如果是{2,4,5,9}呢? median是选4, 还是5? 先看选4的话: $$|2-4| + |4-4| + |5-4| + |9-4| = 8$$, 如果选5呢: $$|1-8|+|4-8|+|9-8| +|10-8| = 8$$. 结果是一样的. 待也可以这样看: sum = 4-2+4-4+5-4+9-4 = (9-2)+(5-4) = 8.
  • 这样就可以将odd/even的情况合并: 即sum = 两头的差之和直到相遇或者相邻.
  • 代码如下:
public int minTotalDistance(int[][] grid) {
    List<Integer> XX = new ArrayList<>();
    List<Integer> YY = new ArrayList<>();
    int M = grid.length, N = grid[0].length;
    for (int i = 0; i < M; ++i) {
      for (int j = 0; j < N; ++j) {
        if (grid[i][j] == 1) {
          XX.add(i);  // 注意这样是映射到y.
        }
      }
    }

    for (int j = 0; j < N; ++j) {
      for (int i = 0; i < M; ++i) {
        if (grid[i][j] == 1) {
          YY.add(j);  // 这里是映射到x. 可以看到loop的顺序保证了映射都是自然排好序的.
        }
      }
    }

    int[] XXArr = new int[XX.size()];
    for (int i = 0; i < XX.size(); ++i) {
      XXArr[i] = XX.get(i);
    }

    int[] YYArr = new int[YY.size()];
    for (int i = 0; i < YY.size(); ++i) {
      YYArr[i] = YY.get(i);
    }

    int Xsum = minTotalDistance1d(XXArr);
    int Ysum = minTotalDistance1d(YYArr);
    return Xsum + Ysum;
  }

  /**
   * 我有意使用了1d的method, 这样可以看作是2D复用1d的解
   * Nice! This simple solution solved the issue that need to compare sum when even size!
   */
  public int minTotalDistance1d(int[] grid) {
    int sum = 0;
    int i = 0, j = grid.length - 1;
    while (i < j) {
      sum += grid[j--] - grid[i++];
      //sum += grid[j] - grid[i];
      //i++;
      //j--;
    }
    return sum;
  }

总结

  • 这种optimization的题目有2个思路:
    1. DP解: DP题
    2. 数学规律: gas station. 所以常见的数学定理还是要知道的.