62. Unique Paths / 63. Unique Paths II

2019-11-10 19:07:47

字体：大中小

来源：转载

供稿：网友

Unique Paths题目描述解法描述Unique Paths II题目描述实现代码

62. Unique Paths

题目描述

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; }};

63. Unique Paths II

题目描述

Follow up for "Unique Paths":Now consider if some obstacles are added to the grids. How many unique paths would there be?An obstacle and empty space is marked as 1 and 0 respectively in the grid.For example,There is one obstacle in the middle of a 3x3 grid as illustrated below.[ [0,0,0], [0,1,0], [0,0,0]]The total number of unique paths is 2.Note: m and n will be at most 100.

实现代码

class Solution {public: int uniquePathsWithObstacles(vector<vector<int>>& g) { int row = g.size(); int column = row > 0?g[0].size():0; int v[101][101] = {0}; v[1][1] = 1 - g[0][0]; for(int i = 1; i <= row; i++) { for(int j = 1; j <= column; j++) { if((i != 1 || j != 1) && g[i-1][j-1]) v[i][j] = 0; else v[i][j] += v[i-1][j] + v[i][j-1]; } } return v[row][column]; }};

上一篇：POJ 2342 Anniversary party (最基础树形DP入门)

下一篇：VC获取屏幕分辨率