Unique Paths題目描述解法描述Unique Paths II題目描述實現代碼
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?
一個矩陣mxn，從左上角到右下角有多少條路徑。
法一：使用深度搜索。這種方法會超時。
class Solution {public: void uniquePathsNum(int &res, int m, int n, int i, int j, int stt) { if(i > m || j > n) return; if(stt >= m+n - 2) { if(m == i && n == j) {res++; return;} else return; } uniquePathsNum(res, m, n, i+1, j, stt+1); uniquePathsNum(res, m, n, i, j+1, stt+1); } int uniquePaths(int m, int n) { int res = 0; uniquePathsNum(res, m, n, 1, 1, 0); return res; }};法二：使用DP來計算。
class Solution {public: int uniquePaths(int m, int n) { /* int **tmp = new int*[m+1]; for(int k = 0; k <= m; k++) tmp[k] = new int[n+1]; */ int tmp[101][101] = {0}; tmp[1][1] = 1; // cout << tmp[0][1] << endl; for(int i = 1; i <= m; i++) { for(int j = 1; j <= n; j++) { tmp[i][j] += (tmp[i-1][j] + tmp[i][j-1]); // cout << i << " " << j << " " << tmp[i][j] << " " << tmp[i-1][j] << " " << tmp[i][j-1] << endl; } } int res = tmp[m][n]; /* for(int i = 0; i <= m; i++) delete tmp[i]; delete tmp; */ return res; }};使用空間復雜度O(n)的代碼：
class Solution {public: int uniquePaths(int m, int n) { int *memo = new int[n]; for(int i = 0; i < n; i++) memo[i] = 1; for(int i = 1 ; i < m; i++) for(int j = 1; j < n; j++) memo[j] += memo[j-1]; return memo[n-1]; }};當然這道題還有方法，那就是使用高中學過的排列組合。
class Solution {public: int uniquePaths(int m, int n) { if(m == 1 || n == 1) return 1; m--; n--; if(m < n) { // Swap, so that m is the bigger number m = m + n; n = m - n; m = m - n; } long res = 1; int j = 1; for(int i = m+1; i <= m+n; i++, j++){ // Instead of taking factorial, keep on multiply & divide res *= i; res /= j; } return (int)res; }};class Solution {public: int uniquePaths(int m, int n) { return nCr (m + n - 2, min(m, n) - 1); }PRivate: int nCr (int n, int r) { long long_result = 1; for (int i = 0; i != r; ++i) { // from n - r + 1 (when i = 0) to n (when i = r - 1) long_result *= (n - r + 1 + i); // from 1 (when i = 0) to r (when i = r - 1) long_result /= (i + 1); } return (int) long_result; }};新聞熱點
疑難解答
