ដំណោះស្រាយឡេឡេកូដកូដតែមួយគត់


កម្រិតលំបាក មធ្យម
សួរញឹកញាប់ កម្មវិធី Adob ​​e ក្រុមហ៊ុន Amazon ផ្លែប៉ោម ទីភ្នាក់ងារ Bloomberg ByteDance Facebook ក្រុមហ៊ុន Goldman Sachs ក្រុមហ៊ុន google ការងារគណិតវិទ្យា ក្រុមហ៊ុន Microsoft ក្រុមហ៊ុន Oracle Qualtrics ការលក់ Snapchat Uber VMware បន្ទប់ពិសោធន៍វ៉លម៉ាត
អារេ ការសរសេរកម្មវិធីឌីណាមិក

បញ្ហាផ្លូវតែមួយគត់ដែលមាន Leetcode ដំណោះស្រាយបញ្ជាក់ថាអ្នកត្រូវបានផ្តល់ឱ្យចំនួនគត់ចំនួនពីរដែលតំណាងឱ្យទំហំនៃក្រឡាចត្រង្គ។ ការប្រើទំហំរបស់ ក្រឡាចត្រង្គប្រវែងនិងទទឹងនៃក្រឡាចត្រង្គ។ យើងត្រូវរកចំនួនផ្លូវប្លែកៗពីជ្រុងខាងឆ្វេងខាងលើនៃក្រឡាចត្រង្គទៅជ្រុងខាងស្តាំខាងក្រោម។ មានឧបសគ្គមួយទៀតលើទិសដៅនៃចលនានៅពេលណាមួយពេលវេលាអាចធ្វើចលនាបានតែក្នុងទិសដៅធ្លាក់ចុះឬទៅស្តាំ។

ឧទាហរណ៍

row: 2, column: 2
2

ការពន្យល់៖ មានតែវិធីពីរទេដែលអាចធ្វើបានដើម្បីបំពេញភារកិច្ច។ ដំបូងអ្នកផ្លាស់ទីទៅស្តាំឬចុះក្រោម។ ប្រសិនបើអ្នកផ្លាស់ទៅស្តាំអ្នកអាចរើចុះក្រោមបាន។ ប្រសិនបើអ្នកបានផ្លាស់ប្តូរចុះក្រោមបន្ទាប់មកអ្នកអាចផ្លាស់ទីបានតែក្នុងទិសដៅធ្លាក់ចុះ។ ដូច្នេះមានតែវិធី ២ ទេដែលអាចធ្វើទៅបាន។

ដំណោះស្រាយឡេឡេកូដកូដតែមួយគត់

row: 2, column: 3
3

ការពន្យល់៖ មាន ៦ វិធីដើម្បីទៅដល់គោលដៅ។ ពិចារណាប្រសិនបើអ្នកផ្លាស់ប្តូរទៅខាងស្តាំបន្ទាប់មកបញ្ហាត្រូវបានកាត់បន្ថយទៅឧទាហរណ៍ខាងលើហើយអ្នកមានវិធី ២ យ៉ាងដើម្បីទៅដល់ជ្រុងខាងស្តាំខាងក្រោម។ ប្រសិនបើអ្នកនឹងធ្លាក់ចុះបន្ទាប់មកអ្នកមានវិធីតែមួយគត់ដើម្បីឈានដល់ជ្រុងខាងស្តាំខាងក្រោម។ ដូច្នេះចំនួនសរុបនៃវិធីដើម្បីឈានដល់ទីបញ្ចប់គឺ ៣ ។

វិធីសាស្រ្តរបស់ Brute Force សំរាប់ដំណោះស្រាយដែលមានតែមួយគត់ Leetcode

បញ្ហាតែមួយគត់ដែលជាមធ្យោបាយដោះស្រាយឡេឡេកូដអាចត្រូវបានដោះស្រាយឡើងវិញ។ ដូចយើងបានធ្វើនៅក្នុងឧទាហរណ៍ទី ២ ដែលយើងបានកាត់បន្ថយបញ្ហាដែលបានផ្តល់ជាអនុសញ្ញាណរងចំនួន ២ ។ រឿងដដែលនេះគឺជាអ្វីដែលយើងនឹងធ្វើក្នុងដំណោះស្រាយនេះ។ នៅពេលមួយយើងផ្លាស់ទៅខាងស្តាំបន្ទាប់មកបញ្ហាត្រូវបានកាត់បន្ថយទៅជាអនុសញ្ញាណរង (ជួរដេកជួរឈរ -១) ។ ប្រសិនបើយើងបានផ្លាស់ប្តូរទិសដៅធ្លាក់ចុះបញ្ហាត្រូវបានកាត់បន្ថយទៅជា (ជួរទី ១ ជួរឈរ) ។ យើងអាចសរសេរកូដដំណោះស្រាយនេះបានយ៉ាងងាយស្រួល។ ប៉ុន្តែនេះនឹងលើសពីដែនកំណត់ពេលវេលាពីព្រោះដំណោះស្រាយមិនមានប្រសិទ្ធភាពខ្លាំង។

លេខកូដសម្រាប់វិធីសាស្រ្តកម្លាំង Brute

លេខកូដ 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

ចាវ៉ាកូដ

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 ^ អតិបរមា (ម, n)), ដោយសារតែភាពស្មុគស្មាញនៃស្វ័យគុណពេលវេលាដោយសារមុខងារហៅខ្លួនឯង។

ភាពស្មុគស្មាញនៃលំហ

O (អតិបរមា (ម, ន), ចន្លោះប្រើដោយជង់ចងក្រង។ នេះអាស្រ័យលើកម្ពស់នៃដើមឈើដែលហៅខ្លួនឯង។

វិធីសាស្រ្តសរសេរកម្មវិធីឌីណាមិក

វិធីសាស្រ្តដែលត្រូវបានពន្យល់ខាងលើក្រោមដំណោះស្រាយដែលអាចរកបានអាចត្រូវបានចងចាំយ៉ាងងាយស្រួល។ ចាប់តាំងពីមុខងារហៅឡើងវិញគឺពឹងផ្អែកលើអថេរពីរដែលជួរដេកនិងជួរឈរ។ ដូច្នេះយើងបង្កើតឌីអេសឌីឌី អារេ និងរក្សាទុកលទ្ធផលនៃរដ្ឋនីមួយៗ។ នេះនឹងធ្វើឱ្យប្រសើរឡើងនូវពេលវេលាស្មុគស្មាញពីព្រោះយើងមិនត្រូវបានដោះស្រាយបញ្ហាដូចគ្នាទេ។

កូដកម្មវិធីឌីណាមិកសម្រាប់ដំណោះស្រាយប្លែកពីឡេឡេកូដ

លេខកូដ 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

ចាវ៉ាកូដ

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), កន្លែងដែលត្រូវការគឺបង្កើតតារាងឌី។ ភី។ ឌី។ អេ។ ភាពស្មុគស្មាញនៃលំហគឺមានពហុធាសម្រាប់វិធីសាស្រ្តឌីភី។