独特路径Leetcode解决方案


难度级别 中等
经常问 土砖 亚马逊 Apple 彭博 ByteDance Facebook 高盛 谷歌 数学作品 微软 神谕 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列)。 我们可以轻松编写此递归解决方案的代码。 但这将超过时间限制,因为解决方案的效率极低。

蛮力进近法典

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)。

空间复杂度

O(N * M), 所需的空间是用于创建2D DP表的空间。 对于DP方法,空间复杂度是多项式。