62. Unique Paths \ 63. Unique Paths II

• 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 - ) {
            if(m == i && n == j) {res++; return;}
            else return;
        }    

        uniquePathsNum(res, m, n, i+, j, stt+);
        uniquePathsNum(res, m, n, i, j+, stt+);
    }

    int uniquePaths(int m, int n) {
        int res = ;
        uniquePathsNum(res, m, n, , , );

        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[][] = {};
        tmp[][] = ;
        // cout << tmp[0][1] << endl;

        for(int i = ; i <= m; i++) {
            for(int j = ; j <= n; j++) {
                tmp[i][j] += (tmp[i-][j] + tmp[i][j-]);
               // 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 = ; i < n; i++)
            memo[i] = ;
        for(int i =  ; i < m; i++)
            for(int j = ; j < n; j++)
                memo[j] += memo[j-];
        return memo[n-];
    }
};
           

當然這道題還有方法，那就是使用高中學過的排列組合。

class Solution {
public:
    int uniquePaths(int m, int n) {
        if(m ==  || n == )
            return ;
        m--;
        n--;
        if(m < n) {              // Swap, so that m is the bigger number
            m = m + n;
            n = m - n;
            m = m - n;
        }
        long res = ;
        int j = ;
        for(int i = m+; 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 - , min(m, n) - );
    }

private:
    int nCr (int n, int r) {
        long long_result = ;
        for (int i = ; i != r; ++i) {
            // from n - r + 1 (when i = 0) to n (when i = r - 1)
            long_result *= (n - r +  + i);
            // from 1 (when i = 0)         to r (when i = r - 1)
            long_result /= (i + );
        }
        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  and  respectively in the grid.

For example,
There is one obstacle in the middle of a x3 grid as illustrated below.

[
  [,,],
  [,,],
  [,,]
]
The total number of unique paths is 

Note: m and n will be at most 
           

實作代碼

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& g) {
        int row = g.size();
        int column = row > ?g[].size():;
        int v[][] = {};
        v[][] =  - g[][];

        for(int i = ; i <= row; i++) {
            for(int j = ; j <= column; j++) {
                if((i !=  || j != ) && g[i-][j-]) v[i][j] = ;
                else v[i][j] += v[i-][j] + v[i][j-]; 
            }
        }

        return v[row][column];
    }
};