独特路径Leetcode解决方案  


难度级别 中等
经常问 土砖 亚马逊 Apple 彭博 ByteDance Facebook 高盛 谷歌 数学作品 微软 神谕 Qualtrics Salesforce的 Snapchat 尤伯杯 VMware的 沃尔玛实验室
算法 排列 编码 动态编程 访谈 面试准备 力码 力码解决方案

问题“唯一路径Leetcode解决方案”指出,您得到了两个表示网格大小的整数。 使用的大小 ,网格的长度和宽度。 我们需要找到从网格左上角到右下角的唯一路径数。 运动方向存在另一个限制,在任何时间点,只能沿向下或向右方向运动。

使用案列  

row: 2, column: 2
2

说明:只有两种方法可以完成任务。 首先,您可以向右或向下移动。 如果您向右移动,则只能向下移动。 如果您已向下移动,则只能沿向下方向移动。 因此,只有两种方法是可能的。

独特路径Leetcode解决方案Pin

row: 2, column: 3
3

说明:有6种到达目的地的方式。 考虑一下是否移至右侧,则问题已归结为上述示例,并且您有两种方法可以到达右下角。 如果您情绪低落,那么只有一种方法可以到达右下角。 因此,到达终点的方式总数为2。

参见
通过串联Leetcode解决方案检查阵列形成

独特路径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解决方案

独特路径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方法,空间复杂度是多项式。