【題目描述】
A robot is located at the top-left corner of amxngrid.
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid.
How many possible unique paths are there?
有一個機器人的位于一個m×n個網(wǎng)格左上角。
機器人每一時刻只能向下或者向右移動一步。機器人試圖達到網(wǎng)格的右下角。
問有多少條不同的路徑？
【注】：n和m均不超過100
【題目鏈接】
www.lintcode.com/en/problem/unique-paths/
【題目解析】
這題是一道典型的dp問題，如果機器人要到(i, j)這個點，它可以選擇先到(i - 1, j)或者，(i, j - 1)，也就是說，到(i, j)的唯一路徑數(shù)等于(i - 1, j)加上(i, j - 1)的個數(shù)，所以我們很容易得出dp方程:dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
dp[i][j]表示從點(0, 0)到(i, j)唯一路徑數(shù)量。
【參考答案】
