62. 不同路径

题意：

解题思路：

思路：
动态规划
状态：定义dp[i][j]表示到达[i, j]位置的路径总和；
状态转移方程：dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
初始化(第一行和第一列只有一条路可走)：dp[i][0] = 1; dp[0][j] = 1;

PHP代码实现：

class Solution {
    /**
     * @param Integer $m
     * @param Integer $n
     * @return Integer
     */
    function uniquePaths($m, $n) {
        $dp = [];
        for ($i = 0; $i < $m; $i++) $dp[0][$i] = 1;
        for ($i = 0; $i < $n; $i++) $dp[$i][0] = 1;
        for ($i = 1; $i < $n; $i++)
            for ($j = 1; $j < $m; $j++)
                $dp[$i][$j] = $dp[$i - 1][$j] + $dp[$i][$j - 1];
        return $dp[$n - 1][$m - 1];
    }
    function uniquePaths1($m, $n) {
       $memo = array_fill(0, $n, array_fill(0, $m, 0));
       $memo[0][0] = 1;
       return $this->helper1($m - 1, $n - 1, $memo);
       return helper(m, n);
    } 
    function helper($m, $n) {
        //到达终点 总数 + 1
        if ($m == 1 && $n == 1) return 1;
        $res = 0;
        if ($m > 0) $res += $this->helper($m - 1, $n);
        if ($n > 0) $res += $this->helper($m, $n - 1);
        return $res;
    }
    function helper1($m, $n, $memo) {
        if ($m == 0 && $n == 0) return 1;
        if ($memo[$m][$n] != 0) return $memo[$m][$n];
        if ($m > 0) $memo[$m][$n] += $this->helper1($m - 1, $n, $memo);
        if ($n > 0) $memo[$m][$n] += $this->helper1($m, $n - 1, $memo);
        return $memo[$m][$n];
    }
}

GO代码实现：

func uniquePaths(m int, n int) int {
    if m <= 0 || n <= 0 {
        return 0
    }
    dp := make([][]int, m)
    for i := 0; i < m; i++ {
        dp[i] = make([]int, n)
        dp[i][0] = 1 
    }
    for i := 0; i < n; i++ {
        dp[0][i] = 1
    } 
    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
        }
    }
    return dp[m-1][n-1]
}