二维矩阵由左上角到右下角只能向右或向下走所有可能路径取值之和最大值，来自网友发的腾讯的一道题目。

matrix = [

  [0, 0, 8, 0, 0],  [0, 0, 0, 9, 0],  [0, 7, 0, 0, 0],  [0, 0, 6, 0, 0]]

我用Haskell实现了一下：

分三步实现，第一步倒推所有可能路径，第二步，反向倒推的路径，得到正向路径，如果只是求和，这一步可以省略。

第三步，对应坐标到具体的路径中，然后求和，获取最大值。没有用到matrix包，只用二维列表来实现。

结果地址：  

不过我不确定计算的路径是否正确，所以又写了一个js的路径绘制动画来验证结果：  

可以直接把Haskell输出的结果粘贴到里面验证，验证了一下基本应该没什么问题。

m X n 矩阵的所有可能路径，当m,n分别取值：(1,1), (1,2), (2,2), (2,3), (3,3), (3,4), (4,4), (4,5), (5,5), (5,6), (6,6)

得到的路径数量依次为：1,1,2,3,6,10,20,35,70,126,252 看起来好像是某个数列？ 也是好多年不写算法了，竟然都推不出路径对应的数学公式了！搜索到一个公式：(m-1 + n-1)! / (m-1)!(n-1)!   即：m+n-2的阶乘 除以 m-1的阶乘和n-1的阶乘的乘积。后面的应该加小括号括起来：

我写了一段Haskell来验证一下这个公式的结果：

 

输出结果为：

[(1,1),(1,2),(2,2),(2,3),(3,3),(3,4),(4,4),(4,5),(5,5),(5,6),(6,6),(6,7),(7,7),(7,8),(8,8),(8,9),(9,9),(9,10),(10,10),(10,11)]

[1,1,2,3,6,10,20,35,70,126,252,462,924,1716,3432,6435,12870,24310,48620,92378]

还有人用c++写了一个路径计算公式：  

我拿来改了一下验证了结果应该没错。