Coin Change 2 Leetcode Solution

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Çiy kərpic Amazon alma Bloomberg ByteDance Cisco Citadel Facebook google microsoft TCS Über
Geyim Dinamik proqramlaşdırma Goldmann SachsBaxılıb 107

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

The Coin Change 2 LeetCode Həlli – “Coin Change 2” fərqli tam ədədlər massivinin verildiyini bildirir coins və tam ədəd amount, pulun ümumi məbləğini təmsil edir.

Bizə cəm edən müxtəlif mümkün birləşmələrin ümumi sayının sayını qaytarmalıyıq amount. Qeyd edək ki, hər bir növün sonsuz sayda sikkəsi var.

Misal:

Input:  amount = 5, coins = [1,2,5]
Output: 4

Explanation:

  • Cəmi 5 olan bütün mümkün birləşmələr bunlardır: [[5], [2,2,1], [2,1,1,1], [1,1,1,1,1]].
Input:  amount = 3, coins = [2]
Output:0

Explanation:

  • Cəmi 3 olan heç bir kombinasiya yoxdur.

Yanaşma

İlk j sikkələrdən istifadə edərək i məbləğini əldə etmək üçün dp[i][j] komboların sayı olsun.

Əsas iş: dp[0][j] = bütün j üçün 0, çünki həmişə 0 sikkə düzəltməyin bir yolu var. Rekursiv hal: i məbləğini etmək üçün ya j-ci sikkədən istifadə edirik, ya da istifadə etmirik. i məbləği etmək üçün kombinlərin ümumi sayı iki halın cəmidir.

- 1-ci hal, j sikkəsindən istifadə etməyin: Biz j sikkəsindən istifadə etmirik, lakin qalan j-1 sikkələrindən hələ də istifadə edə bilərik. İlk j-1 sikkələrindən istifadə edərək i məbləğini əldə etmək üçün dp[i][j-1] kombinləri var.

– 2-ci hal, j sikkəsindən istifadə edin: j-ci sikkə c olsun. Əvvəlki məbləğə c əlavə edərək cari məbləği edirik. Əvvəlki məbləğ i – c olduğundan, ilk j sikkələrdən istifadə edərək i məbləğini yaratmaq üçün dp[ic][j] kombinasiyaları var.

Cavab bütün sikkələrdən istifadə edərək hədəf məbləği əldə etməyin yollarının sayıdır, dp[amount][coins.size()]

Idea:

  1. Bu problemi həll etmək üçün əsas fikir istifadə etməkdir dinamik proqramlaşdırma.
  2. Gəlin dp[i] = cəmi i-ə bərabər olan birləşmələrin ümumi sayı.
  3. Əsas vəziyyət: dp[0] = 1.
  4. İndi, hər x sikkəsi üçün xətti dp massivində təkrarlayın və hər i üçün dp[ix]-i dp[i]-yə əlavə edin, çünki (ix) vəziyyətindən i vəziyyətinə gələ bilərik.
  5. Nəhayət, qayıt dp[miqdar] cavabımız budur.

Coin Change 2 Leetcode SolutionPin

Kodu

C++ Həlli:

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount+1);
        dp[0] = 1;
        for(auto& x:coins){
            for(int i=x;i<=amount;i++){
                dp[i] += dp[i-x];
            }
        }
        return dp[amount];
    }
};

Java Həlli:

class Solution {
    public int change(int amount, int[] coins) {
        int dp[] = new int[amount+1];
        for(int i=0;i<=amount;i++){
            dp[i] = 0;
        }
        dp[0] = 1;
        for(int i=0;i<coins.length;i++){
            for(int j=coins[i];j<=amount;j++){
                dp[j] += dp[j-coins[i]];
            }
        }
        return dp[amount];
    }
}

Coin Change 2 Leetcode Solution üçün Mürəkkəblik Təhlili

Zamanın mürəkkəbliyi

Yuxarıdakı kodun zaman mürəkkəbliyi O(N*məbləğ) çünki, hər bir sikkə üçün biz iterasiya edirik məbləği dəfə sayı.

Kosmik Mürəkkəblik

Yuxarıdakı kodun məkan mürəkkəbliyi O(miqdar)-dir, çünki biz xətti yaradırıq dinamik proqramlaşdırma massiv ölçüsü məbləği.

Crack Sistemi Dizayn Müsahibələri
Translate »