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?

題目大意

在一個m*n的表格中舷蒲，從左上角的起點處走到右下角的終點處共有多少條不同的路徑扮超。
在本題中举反，上圖中的表格是3*7的一個表格譬正，有多少種不同的路徑放坏。

思路

動態(tài)規(guī)劃思想

這是一個典型的入門級動態(tài)規(guī)劃問題哮针，很容易想到動態(tài)規(guī)劃的思路巩螃。

二維數(shù)組動態(tài)規(guī)劃

把問題中的m*n的表格翻譯成m*n的二維數(shù)組，原理是除了第一行或者第一列的格子外大诸，到其他格子路徑的走法是：每一個格子的可到達路徑數(shù)=左邊一個格子的可到達路徑數(shù)+上邊一個格子的可到達路徑數(shù)（第一行或者第一列的格子到達的路徑數(shù)均為1）捅厂。時間復(fù)雜度為O(N^2)， 空間復(fù)雜度為O(N^2)资柔。

一維數(shù)組動態(tài)規(guī)劃

用一維數(shù)組代替二維數(shù)組焙贷，動態(tài)更新。時間復(fù)雜度為O(N^2)贿堰，空間復(fù)雜度為O(N)盈厘。

組合數(shù)學(xué)思想

組合數(shù)學(xué)的思想是，從左上角的起點處走到右下角的終點處官边，只能向右走或者只能向下走，從行上看走過了m - 1行外遇，從列上看走過了n - 1列注簿，即可以理解為排列組合的問題，所以一共需要的步數(shù)中挑出m - 1個向下走跳仿，剩下的n - 1個就是向右走诡渴，其實就是從（m-1+n-1）里挑選（n-1）或者（m-1）個，即：C(n,r)菲语，其中n = （m-1+n-1）妄辩，r = （n-1）或者r = （m-1），公式為：n! / ( r! * (n - r)! )山上。

代碼

動態(tài)規(guī)劃（二維數(shù)組）

int uniquePaths(int m, int n) {
    // 用vector定義int類型的二維數(shù)組眼耀，并全部初始化為1
    vector<vector<int > > dp(m, vector<int >(n, 1));
    for(int i=1; i<m; i++)
    {
        for(int j=1; j<n; j++)
        {
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }//for
    }//for
    return dp[m-1][n-1];
}

動態(tài)規(guī)劃（一維數(shù)組）

int uniquePaths(int m, int n) {
    // 用vector定義int類型的一維數(shù)組，并全部初始化為1
    vector<int > dp(n, 1);
    for(int i=1; i<m; i++)
    {
        for(int j=1; j<n; j++)
        {
            // 用一維數(shù)組模擬二維數(shù)組佩憾，動態(tài)更新當(dāng)前行
            dp[j] += dp[j-1];
        }//for
    }//for
    return dp[n-1];
}

組合數(shù)學(xué)（排列組合）

int uniquePaths(int m, int n) 
{
    long x = m+n-2;// 不用 long 會溢出哮伟，階乘求出來太大了
    long y = min(m,n)-1;
    long up = 1,down =1;// 最后求組合數(shù)的分子 / 分母
    // if(m==1||n==1) return 1;
    for(int i = 0;i<y ;i++)
    {
        up *= x--;
    }
    for(int i = y; i>0; i--)
    {
        down *= i;
    }
    return int(up/down);
}

以上干花。

版權(quán)聲明：本文為博主原創(chuàng)文章，轉(zhuǎn)載請注明出處楞黄。
個人博客地址：https://yangyuanlin.club
歡迎來踩~~~~