不同路径

题目描述：

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

问总共有多少条不同的路径？

示例:

例如，上图是一个7 x 3 的网格。有多少可能的路径？

说明：m和 n 的值均不超过 100。

示例 1:

输入:m = 3, n = 2   输出:3

解释:从左上角开始，总共有 3 条路径可以到达右下角。1. 向右 -> 向右 -> 向下2. 向右 -> 向下 -> 向右3. 向下 -> 向右 -> 向右

分析：

题目里面显示只能往下或者往右，那么每个格子都只能从上面格子或者左边格子走过，因此f(m)(n) = f(m)(n-1) + f(m-1)(n)，m表示行，n表示列。但是也有特例，对于对于第一列和第一行他们都只有一种路径，即f(m)(1) = f(1)(n) = 1；

编码：

function uniquePaths($m, $n) {

    $result = [];

    for ($i = 0; $i < $m; $i++) {

        for ($j = 0; $j < $n; $j++) {

            if ($i == 0 || $j == 0) {

                $result[$i][$j] = 1; //处理第一行和第一列的特殊情况

            } else {

                $result[$i][$j] = $result[$i-1][$j] + $result[$i][$j-1];

            }

        }

    }

    return $result[$m-1][$n-1];

}