โซลูชัน Leetcode เส้นทางที่ไม่ซ้ำใคร


ระดับความยาก กลาง
ถามบ่อยใน อะโดบี อเมซอน แอปเปิล บลูมเบิร์ก ByteDance Facebook แซคส์โกลด์แมน Google คณิตศาสตร์ ไมโครซอฟท์ คำพยากรณ์ Qualtrics Salesforce Snapchat Uber VMware Walmart Labs
แถว การเขียนโปรแกรมแบบไดนามิก

ปัญหา Unique Paths Leetcode Solution ระบุว่าคุณได้รับจำนวนเต็มสองจำนวนที่แสดงขนาดของเส้นตาราง โดยใช้ขนาดของไฟล์ ตะแกรงความยาวและความกว้างของเส้นตาราง เราต้องหาจำนวนเส้นทางที่ไม่ซ้ำกันจากมุมบนซ้ายของตารางไปที่มุมล่างขวา มีข้อ จำกัด อีกประการหนึ่งเกี่ยวกับทิศทางการเคลื่อนที่ในช่วงเวลาใดเวลาหนึ่งเราสามารถเคลื่อนที่ได้เฉพาะในทิศทางลงหรือทิศทางที่ถูกต้องเท่านั้น

ตัวอย่าง

row: 2, column: 2
2

คำอธิบาย: มีเพียงสองวิธีที่เป็นไปได้ในการทำงานให้เสร็จสิ้น ขั้นแรกให้คุณเลื่อนไปทางขวาหรือลง หากคุณย้ายไปทางขวาคุณสามารถเลื่อนลงได้เท่านั้น หากคุณเลื่อนลงคุณสามารถย้ายไปในทิศทางลงเท่านั้น มีเพียง 2 วิธีเท่านั้นที่เป็นไปได้

โซลูชัน Leetcode เส้นทางที่ไม่ซ้ำใคร

row: 2, column: 3
3

คำอธิบาย: มี 6 วิธีในการไปถึงจุดหมายปลายทาง พิจารณาว่าคุณย้ายไปทางขวาหรือไม่แสดงว่าปัญหาได้ลดลงตามตัวอย่างด้านบนแล้วและคุณมี 2 วิธีในการเข้าถึงมุมขวาล่าง หากคุณจะลงคุณมีทางเดียวที่จะไปถึงมุมขวาล่าง ดังนั้นจำนวนวิธีทั้งหมดที่จะไปถึงจุดสิ้นสุดคือ 3

แนวทาง Brute Force สำหรับเส้นทางที่ไม่ซ้ำ Leetcode Solution

ปัญหา Unique Paths Leetcode Solution สามารถแก้ไขซ้ำได้ เช่นเดียวกับที่เราทำในตัวอย่างที่สองซึ่งเราลดปัญหาที่กำหนดให้เป็น 2 ปัญหาย่อย สิ่งเดียวกันคือสิ่งที่เราจะทำในการแก้ปัญหานี้ เมื่อเราเลื่อนไปทางขวาจากนั้นปัญหาจะลดลงเป็นปัญหาย่อย (แถวคอลัมน์ -1) หากเราเคลื่อนไปในทิศทางลงปัญหาจะลดลงเป็น (row-1, column) เราสามารถเขียนโค้ดโซลูชันแบบวนซ้ำนี้ได้อย่างง่ายดาย แต่จะเกินเวลาที่กำหนดเนื่องจากการแก้ปัญหาไม่มีประสิทธิภาพอย่างมาก

รหัสสำหรับแนวทาง Brute Force

รหัส 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 ^ สูงสุด (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