獨特路徑Leetcode解決方案  


難度級別 中烘焙
經常問 土磚 亞馬遜 蘋果 彭博社 ByteDance Facebook 高盛 谷歌 Mathworks公司 Microsoft微軟 神諭 Qualtrics Salesforce的 Snapchat 尤伯杯 VMware的 沃爾瑪實驗室
算法 排列 編碼 動態編程 訪問 面試準備 力碼 力碼解決方案

問題“唯一路徑Leetcode解決方案”指出,您得到了兩個表示網格大小的整數。 使用的大小 ,網格的長度和寬度。 我們需要找到從網格左上角到右下角的唯一路徑數。 運動方向存在另一個限制,在任何時間點,只能沿向下或向右方向運動。

例  

row: 2, column: 2
2

說明:只有兩種方法可以完成任務。 首先,您可以向右或向下移動。 如果您向右移動,則只能向下移動。 如果您已向下移動,則只能沿向下方向移動。 因此,只有兩種方法是可能的。

獨特路徑Leetcode解決方案

row: 2, column: 3
3

說明:有6種到達目的地的方式。 考慮一下是否移至右側,則問題已歸結為上述示例,並且您有兩種方法可以到達右下角。 如果您情緒低落,那麼只有一種方法可以到達右下角。 因此,到達終點的方式總數為2。

獨特路徑Leetcode解決方案的蠻力方法  

唯一路徑Leetcode解決方案的問題可以遞歸解決。 就像在第二個示例中所做的一樣,我們將給定的問題簡化為2個子問題。 同樣的事情是我們將在此解決方案中執行的操作。 一次,我們向右移動,然後問題被簡化為子問題(第1行,第1列)。 如果我們朝下方向移動,則問題將歸結為(第XNUMX行,第XNUMX列)。 我們可以輕鬆編寫此遞歸解決方案的代碼。 但這將超過時間限制,因為解決方案的效率極低。

也可以看看
通過串聯Leetcode解決方案檢查陣列形成

蠻力進近法典

C ++代碼

#include <bits/stdc++.h>
using namespace std;

int uniquePaths(int m, int n) {
    if(n==1 || m==1)return 1;
    return uniquePaths(m-1, n) + uniquePaths(m, n-1);
}

int main(){
    cout<<uniquePaths(2, 2);
}
2

Java代碼

import java.util.*;
import java.lang.*;
import java.io.*;

class Solution {
    public static int uniquePaths(int m, int n) {
        if(m == 1 || n == 1)
            return 1;
        return uniquePaths(m-1, n) + uniquePaths(m, n-1);
    }
    
    public static void main(String[] args){
    	System.out.print(uniquePaths(2,2));
    }
}
2

複雜度分析

時間複雜度

O(2 ^ max(m,n)), 由於遞歸函數導致的指數時間複雜度。

空間複雜度

O(最大(m,n), 編譯器堆棧使用的空間。 這取決於遞歸樹的高度。

動態規劃方法  

上面已經在遞歸解決方案下說明的方法可以很容易地記住。 由於遞歸函數取決於兩個變量,分別是行和列。 因此,我們創建了2D DP 排列 並存儲每個狀態的結果。 這將大大提高時間複雜度,因為我們沒有解決相同的問題。

獨特路徑Leetcode解決方案的動態編程代碼

C ++代碼

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> dp;
int uniquePathsUtil(int m, int n) {
    if(m == 1 || n == 1) return 1;
    if(dp[m][n] != -1)
        return dp[m][n];
    return dp[m][n] = uniquePathsUtil(m-1, n) + uniquePathsUtil(m, n-1);
}

int uniquePaths(int m, int n) {
    dp.clear();
    dp.assign(m+1, vector<int>(n+1, -1));
    return uniquePathsUtil(m, n);
}

int main(){
    cout<<uniquePaths(2, 2);
}
2

Java代碼

import java.util.*;
import java.lang.*;
import java.io.*;

class Solution {
    private static int uniquePathsUtil(int m, int n, int[][] dp) {
        if(m == 1 || n == 1) return 1;
        if(dp[m][n] != 0)
            return dp[m][n];
        return dp[m][n] = uniquePathsUtil(m-1, n, dp) + uniquePathsUtil(m, n-1, dp);
    }

    private static int uniquePaths(int m, int n) {
        int dp[][] = new int[m+1][n+1];
        return uniquePathsUtil(m, n, dp);
    }
    
    public static void main(String[] args){
    	System.out.print(uniquePaths(2,2));
    }
}
2

複雜度分析

時間複雜度

O(N * M), 其中N,M用於表示網格中的行數和列數。 由於總共有N * M個狀態,因此時間複雜度也為O(N * M)。

也可以看看
最少時間訪問所有積分Leetcode解決方案

空間複雜度

O(N * M), 所需的空間是用於創建2D DP表的空間。 對於DP方法,空間複雜度是多項式。