leetcode题解 problem 62 63 Unique Paths I & II

Tags:

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?

1 class Solution {
2 public:
3   int uniquePaths(int m, int n) {
4 
5     }
6 };

题意:

求路径总数,每次只能往右或往下走

题解:

入门级别动态规划题目。

列下状态转移方程:

设S(i,j)是从pos(0,0)到pos(i,j)的路径总数。

可得:

S(i, j) = S(i - 1, j) + S(i, j - 1)

方程的含义是:

每个格子的路径总数 等于 起点到它左边的格子的路径总数 + 起点到它上方的格子的路径总数。

代码(0ms RunTime):

 1   int uniquePaths(int m, int n) {
 2      vector<vector<int>> sum(n);
 3      for (int i = 0; i < n; ++i){
 4          sum[i].resize(m);
 5      }
 6      for (int i = 0; i < n; ++i)
 7          sum[i][0] = 1;
 8      for (int i = 0; i < m; ++i)
 9          sum[0][i] = 1;
10 
11      for (int i = 1; i < n; ++i)
12          for (int j = 1; j < m; ++j)
13              sum[i][j] = sum[i - 1][j] + sum[i][j - 1];
14      return sum[n - 1][m - 1];
15  }

对于Unique Paths II,改变点是,有些格子变成了障碍物。其实也很简单,上面的代码稍微改下就好了。

代码(4ms RunTime):

 1   int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
 2      int n = obstacleGrid.size();
 3      int m = obstacleGrid[0].size();
 4      vector<vector<int>> sum(n);
 5      for (int i = 0; i < n; ++i){
 6          sum[i].resize(m);
 7      }
 8      if (obstacleGrid[0][0] == 1)
 9          sum[0][0] = 0;
10      else
11          sum[0][0] = 1;
12      for (int i = 1; i < n; ++i)
13          if (obstacleGrid[i][0] == 1)
14              sum[i][0] = 0;
15          else
16              sum[i][0] = sum[i-1][0];
17 
18      for (int i = 1; i < m; ++i)
19          if (obstacleGrid[0][i] == 1)
20              sum[0][i] = 0;
21          else
22              sum[0][i] = sum[0][i - 1];
23 
24      for (int i = 1; i < n; ++i)
25          for (int j = 1; j < m; ++j){
26              if (obstacleGrid[i][j] == 1)
27                  sum[i][j] = 0;
28              else
29                  sum[i][j] = sum[i - 1][j] + sum[i][j - 1];
30          }
31      return sum[n - 1][m - 1];
32  }
(未经授权禁止转载)
Written on June 27, 2015

博主将十分感谢对本文章的任意金额的打赏^_^