1. 概述

有一个机器人的位于一个 m × n 个网格左上角。 机器人每一时刻只能向下或者向右移动一步。机器人试图达到网格的右下角。

问有多少条不同的路径？

2. 解题

<?php
class Solution {
    /**
     * @param int $m
     * @param int $n
     * @return int : An integer
     */
    public function uniquePaths(int $m, int $n) : int {
        $f = [];
        for ($i = 0; $i < $m; $i++) {
            $f[$i][0] = 1;
        }
        for ($j = 0; $j < $n; $j++) {
            $f[0][$j] = 1;
        }
        for ($i = 1; $i < $m; $i++) {
            for ($j = 1; $j < $n; $j++) {
                $f[$i][$j] = $f[$i][$j - 1] + $f[$i - 1][$j];
            }
        }
        return $f[$m - 1][$n - 1];
    }
}
$cls = new Solution();
$r = $cls->uniquePaths(3, 3);
echo $r;