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?

这题是一道典型的dp问题，如果机器人要到(i, j)这个点，他可以选择先到(i - 1, j)或者，(i, j - 1)，也就是说，到(i, j)的唯一路径数等于(i - 1, j)加上(i, j - 1)的个数，所以我们很容易得出dp方程:

dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

dp[i][j]表示从点(0, 0)到(i, j)唯一路径数量。

代码如下：

  1. class Solution {
  2. public:
  3.     int uniquePaths(int m, int n) {
  4.         int dp[m][n];
  5.         //初始化dp，m x 1情况全为1
  6.         for(int i = 0; i < m; i++) {
  7.             dp[i][0] = 1;
  8.         }
  10.         //初始化dp，1 x n情况全为1
  11.         for(int j = 0; j < n; j++) {
  12.             dp[0][j] = 1;
  13.         }
  15.         for(int i = 1; i < m; i++) {
  16.             for(int j = 1; j < n; j++) {
  17.                 dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
  18.             }
  19.         }
  21.         return dp[m - 1][n - 1];
  22.     }
  23. };

Unique Paths II

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.

这题跟上一题唯一的区别在于多了障碍物，如果某一个点有障碍，那么机器人无法通过。

代码如下:

  1. class Solution {
  2. public:
  3.     int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
  4.         if(obstacleGrid.empty() || obstacleGrid[0].empty()) {
  5.             return 0;
  6.         }
  8.         int m = obstacleGrid.size();
  9.         int n = obstacleGrid[0].size();
  11.         int dp[m][n];
  13.         //下面初始dp的时候需要根据obstacleGrid的值来确定
  14.         dp[0][0] = (obstacleGrid[0][0] == 0 ? 1 : 0);
  16.         //我们需要注意m x 1以及1 x n的初始化
  17.         for(int i = 1; i < m; i++) {
  18.             dp[i][0] = ((dp[i - 1][0] == 1 && obstacleGrid[i][0] == 0) ? 1 : 0);
  19.         }
  21.         for(int j = 1; j < n; j++) {
  22.             dp[0][j] = ((dp[0][j - 1] == 1 && obstacleGrid[0][j] == 0) ? 1 : 0);
  23.         }
  26.         for(int i = 1; i < m; i++) {
  27.             for(int j = 1; j < n; j++) {
  28.                 if(obstacleGrid[i][j] == 1) {
  29.                     dp[i][j] = 0;
  30.                 } else {
  31.                     dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
  32.                 }
  33.             }
  34.         }
  36.         return dp[m - 1][n - 1];
  37.     }
  38. };

Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

这题跟前面两题差不多，所以放到这里说明了。我们使用dp[i][j]表明从(0, 0)到(i, j)最小的路径和，那么dp方程为:

dp[i][j] = min(dp[i][j-1], dp[i - 1][j]) + grid[i][j]

代码如下：

  1. class Solution {
  2. public:
  3.     int minPathSum(vector<vector<int> > &grid) {
  4.         if(grid.empty() || grid[0].empty()) {
  5.             return 0;
  6.         }
  8.         int row = grid.size();
  9.         int col = grid[0].size();
  11.         int dp[row][col];
  13.         dp[0][0] = grid[0][0];
  14.         for(int i = 1; i < row; i++) {
  15.             dp[i][0] = dp[i - 1][0] + grid[i][0];
  16.         }
  18.         for(int j = 1; j < col; j++) {
  19.             dp[0][j] = dp[0][j - 1] + grid[0][j];
  20.         }
  22.         for(int i = 1; i < row; i++) {
  23.             for(int j = 1; j < col; j++) {
  24.                 dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
  25.             }
  26.         }
  28.         return dp[row - 1][col - 1];
  29.     }
  30. };