62.md

:pencil2:基础刷题之(62. Unique Paths)

. 2019-11-15 吴亲库里 库里的深夜食堂

:pencil2:描述

当前机器人位于左上角的位置，每次只能向下或者向右移动一位，求到达网格的右下角有多少种独特的方式

:pencil2:题目实例

​

---

:pencil2:题目分析

这是一个典型的动态规划题型，对于动态规划，之前写过一篇文章，这两天会根据自己的理解，重新再写一篇。动态规划最重要的两步:1.定义状态。2动态转移公式。因为开始的时候向下或者向右都是一条路径。所以 dp[0][i] 和 dp[i][0] 都等于1。然后推导出转移方程。这个转移方程也是根据每次只能向下或者向右移动推导出的。

dp[$i][$j] 表示从(0,0)到(i,j)路径总数。

dp[$i][$j]=$dp[$i-1][$j]+$dp[$i][$j-1]  转移方程

:pencil2:最终实现代码

 /**
     * @param Integer $m
     * @param Integer $n
     * @return Integer
     */
    function uniquePaths($m, $n) {
        
        for($i=0;$i<$m;$i++){
            $dp[$i][0]=1;
        }
        
        for($j=0;$j<$n;$j++){
            $dp[0][$j]=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];
    }

---

联系

​