Leetcode 動態規劃 Unique Paths
來源：程序員人生 發布時間：2014-09-08 17:09:21 閱讀次數：2355次
本文為senlie原創，轉載請保留此地址：http://blog.csdn.net/zhengsenlie
Unique Paths
Total Accepted: 17915 Total
Submissions: 57061My Submissions
A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
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 (marked 'Finish' in the diagram below).
How many possible unique paths are there?
Above is a 3 x 7 grid. How many possible unique paths are there?
Note: m and n will be at most 100.
題意：給定一個 m * n 的網格，一個機器人要從左上角走到右下角，每次只能向下或向右移動一個位置，
問有多少種走法
思路1：dfs暴力枚舉
復雜度：超時了... O(2^n)
思路2：記憶化搜索
用一個數組paths[i][j]記錄從 (0,0) 到 (m,n)的路徑數
思路3：dp
設置狀態為f[i][j]，表示從(0,0)到達網格(i,j)的路徑數，則狀態轉移方程為
f[i][j] = f[i - 1][j] + f[i][j - 1]
復雜度：時間O(n^2) 空間 O(n)
<pre name="code" class="cpp">//思路1
int uniquePaths(int m, int n){
if(m < 0 || n < 0) return 0;
if(m == 1 && n == 1) return 1;
return uniquePaths(m - 1, n) + uniquePaths(m, n - 1);
}
//思路2
//paths[i][j]表示從(0,0)到(i,j）的路徑數
int paths[101][101];
int dfs(int m, int n){
if(m < 0 || n < 0) return 0;
if(m == 1 && n == 1) return 1;
if(paths[m][n] >= 0) return paths[m][n];
return paths[m][n] = dfs(m - 1, n) + dfs(m, n - 1);
}
int uniquePaths(int m, int n){
memset(paths, -1, sizeof(paths));
return dfs(m, n);
}
//思路2另一種寫法
//paths[i][j]表示從(i,j)到(m - 1,n - 1)的路徑數
int paths[101][101];
int mm, nn;
int dfs(int x, int y){
if(x >= mm || y >= nn) return 0;
if(x == mm - 1 && y == nn - 1) return 1;
if(paths[x][y] >= 0) return paths[x][y];
return paths[x][y] = dfs(x + 1, y) + dfs(x, y + 1);
}
int uniquePaths(int m, int n){
mm = m, nn = n;
memset(paths, -1, sizeof(paths));
return dfs(0, 0);
}
//思路3 paths[i][j] 表示(0, 0) 到(i,j)的路徑數
int paths[101][101];
int uniquePaths(int m, int n){
memset(paths, 0, sizeof(paths));
for(int i = 0; i < m; ++i) paths[i][0] = 1;
for(int j = 0; j < n; ++j) paths[0][j] = 1;
for(int i = 1 ; i < m; ++i){
for(int j = 1; j < n; ++j){
paths[i][j] = paths[i - 1][j] + paths[i][j - 1];
}
}
return paths[m - 1][n - 1];
}
思路3 另一種寫法
用一個一維數組 paths[j] 表示 (0, 0) 至 (i, j)的路徑數，在外循環變量為 i 時，還沒更新前
paths[j] 對應上面二維數組寫法的paths[i - 1, j]，paths[j - 1]對應paths[i][j - 1]
int paths[101];
int uniquePaths(int m, int n){
memset(paths, 0, sizeof(paths));
paths[0] = 1;
for(int i = 0; i < m; ++i){
for(int j = 1; j < n; ++j){
paths[j] = paths[j] + paths[j - 1];
}
}
return paths[n - 1];
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
