方格棋盘上的最短路径有关问题，求思路 .

方格棋盘上的最短路径问题，求思路 ......


下学期要学数据结构，老师甩了几道题研究

看到这题的第一想法就是把每一个点都试一遍，但是这样效率肯定很低，老师的提示是用数据结构中“分而治之”算法把二维优化转

化为一维优化问题，班里的大神说是用链表可以解决。

我把看了会书里这部分的内容然而并没有什么头绪，求大神开导下






------解决思路----------------------
要求解的是：

min sum 
------解决思路----------------------
x-xi
------解决思路----------------------
 + 
------解决思路----------------------
y - yi
------解决思路----------------------

因为x,y没有关联，上述目标可以拆分为两个小目标：

min sum 
------解决思路----------------------
x-xi
------解决思路----------------------
 + min sum 
------解决思路----------------------
y-yi
------解决思路----------------------

分别求解这两个一维优化问题即可。一维的解是中位数。
------解决思路----------------------

引用:

要求解的是：
。。。
分别求解这两个一维优化问题即可。一维的解是中位数。

求中位数的算法可以使用线性选择算法，具体参阅算法设计书。
------解决思路----------------------

这是什么算法题？？？这不就是一个求重心的问题么。
学校X = sum(x) / n
学校Y = sum(y) / n