一個機器人位于一個 n * m 網(wǎng)格的左上角 （起始點在下圖中標記為“Start” ）。(n表示行，m表示列)

機器人每次只能向下或者向右移動一步。機器人試圖達到網(wǎng)格的右下角（在下圖中標記為“Finish”）。

問總共有多少條不同的路徑？

數(shù)據(jù)范圍：
n <= 100,m <= 100;

解題思路：
首先我們定義dp[i][j]表示機器人走到（i,j）這個位置的走法總數(shù)，
然后我們想到機器人每次只能向下或者向右移動一步，那么這個位置只可能來自上面走下來的，或者左邊走過來的，故容易想到關(guān)系表達式為dp[i][j] = dp[i-1][j]+dp[i][j-1]，然后我們想想初始化問題，假如i = 0，那么i-1就會為負數(shù)，數(shù)組會越界，我們可以這樣初始化：

for (int i = 0; i < n; i++)dp[i][0] = 1;//相當(dāng)于最左邊那一列，機器人只能往下走，故走法只有一種for (int i = 0; i < m; i++)dp[0][i] = 1;//相當(dāng)于最上面那一行，機器人只能往右走，故走法只有一種

代碼如下：

#include <iostream> using namespace std; const int N = 1010; int dp[N][N];int main() {int n, m;cin >> n >> m;for (int i = 0; i < n; i++)dp[i][0] = 1;for (int i = 0; i < m; i++)dp[0][i] = 1;for (int i = 1; i < n; i++)for (int j = 1; j < m; j++) {dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}cout << dp[n - 1][m - 1] << endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的不同路径 I的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。