Унікальне рішення штрих-коду  


Рівень складності Medium
Часто запитують у саман Амазонка Apple Bloomberg ByteDance Facebook Goldman Sachs Google Математичні роботи Microsoft оракул Qualtrics Salesforce Snapchat Убер VMware Лабораторії Walmart
алгоритми масив кодування Динамічне програмування інтерв'ю інтерв'юпідготовка LeetCode LeetCodeSolutions

У проблемі Unique Paths Leetcode Solution зазначено, що вам дано два цілих числа, що представляють розмір сітки. Використовуючи розмір сітка, довжина та ширина сітки. Нам потрібно знайти кількість унікальних контурів від верхнього лівого кута сітки до нижнього правого кута. Існує одне обмеження напрямку руху, в будь-який момент часу можна рухатися лише внизу або вправо.

Приклад  

row: 2, column: 2
2

Пояснення: Виконати завдання можна лише двома способами. Спочатку ви рухаєтеся вправо або вниз. Якщо ви рухалися вправо, ви можете рухатися лише вниз. Якщо ви рухалися вниз, тоді ви можете рухатися лише в напрямку вниз. Отже, можливі лише 2 способи.

Унікальне рішення штрих-кодуPin

row: 2, column: 3
3

Пояснення: Є 6 способів дістатися до пункту призначення. Подумайте, якщо ви перейшли праворуч, то проблема зведена до наведеного вище прикладу, і у вас є 2 способи дістатися до нижнього правого кута. Якщо ви хочете вниз, то у вас є лише один спосіб дістатися до нижнього правого кута. Таким чином, загальна кількість способів досягти кінця - 3.

Дивись також
Перевірте формування масиву за допомогою рішення об'єднання Leetcode

Підхід грубої сили для вирішення унікальних шляхів Leetcode  

Проблема Унікальні шляхи вирішення шрифтів може бути вирішена рекурсивно. Так само, як ми це зробили у другому прикладі, де ми звели задану задачу на 2 підзадачі. Те саме, що ми будемо робити в цьому рішенні. Одного разу ми рухаємося праворуч, тоді проблема зводиться до підзадачі (рядок, стовпець-1). Якби ми рухались у напрямку вниз, проблема зводиться до (рядок-1, стовпець). Ми можемо легко кодувати це рекурсивне рішення. Але це перевищить обмеження за часом, оскільки рішення є надзвичайно неефективним.

Кодекс підходу грубої сили

Код С ++

#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

Код С ++

#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.