.
2019-11-15 吴亲库里 库里的深夜食堂
当前机器人位于左上角的位置，每次只能向下或者向右移动一位，求到达网格的右下角有多少种独特的方式
这是一个典型的动态规划题型，对于动态规划，之前写过一篇文章，这两天会根据自己的理解，重新再写一篇。动态规划最重要的两步: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] 转移方程
/**
* @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];
}
