1. 概述

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

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

2. 解题

<?php
class Solution {
    public $way = [];
    public $map = [];
    /**
     * @param Integer $m 列
     * @param Integer $n 行
     * @return Integer
     */
    public function uniquePaths($m, $n) {
        if (($m <= 0) && ($n <= 0)) {
            $this->way[] = [];
        } elseif (($m <= 0 && $n > 0) || ($m > 0 && $n <= 0)) {
            $forward = $m > 0 ? 'r' : 'd';
            $way = str_repeat($forward, max($m, $n));
            $way = explode(',', $way);
            $this->way[] = $way;
        } else {
            $map = [];
            for ($i = 0; $i < $n; $i++) {
                for ($j = 0; $j < $m; $j++) {
                    $map[$i][$j] = 1;
                }
            }
            $this->map = $map;
            $this->dp ($n, $m, [0, 0]);
        }
        return count($this->way);
    }
    private function dp ($n, $m, $last, $way = []) {
        if ($last == [$n - 1, $m - 1]) {
            $this->way[] = $way;
            return;
        }
        if (isset($this->map[$last[0]][$last[1] + 1])) {    // 右
            $way[] = 'r';
            $this->dp($n, $m, [$last[0], $last[1] + 1], $way);
            array_pop($way);
        }
        if (isset($this->map[$last[0] + 1][$last[1]])) {    // 下
            $way[] = 'd';
            $this->dp($n, $m, [$last[0] + 1, $last[1]], $way);
            array_pop($way);
        }
    }
}
$m = 0;
$n = 3;
$cls = new Solution();
$r = $cls->uniquePaths($m, $n);
echo $r;
array_walk($cls->map, function(&$v) {
    $v = implode(',', $v);
});
print_r($cls->map);
array_walk($cls->way, function(&$v) {
    $v = implode(',', $v);
});
print_r($cls->way);