Hədəf cəmi

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon Bloomberg Facebook
Dərinlik İlk Axtarış Dinamik proqramlaşdırmaBaxılıb 39

“Hədəf cəmi” bu gün yanımda olan bütün DPHolics üçün xüsusi bir problemdir. Mənim sevimli oxucularımın qalan hissəsini tərk edəcəyim üçün narahat olmağa ehtiyac yoxdur. Hamımız klassik bir KnapSack problemini keçdik, burada çuvala sındırmadan maksimum miqdarda əşyalarınızı tapmağa çalışdıq.

Beləliklə, daha gecikmədən. Problemə gələk. Bu gün mənimlə eyni istifadə edən bir problem var.

Problem bəyanat

Verilmişdir: An array elementlər və hədəf cəmi ilə əldə etməliyik

Şərtlər:

  • Elementləri bir-birimizlə əlavə və ya çıxartmağımıza icazə verilir
  • Hədəfimizə çatmaq üçün mövcud məbləğlə + və ya istifadə edə bilərsiniz.

Çıxış necə olmalıdır?

Hədəfə çatmağımızın sayı

Nümunə Array: [1,1,1,1,1]

Hədəf_sum: 3

Yanaşma-1

Hədəf məbləğini tapmaq üçün düz Jane rekursiyası

Bu yanaşma, mümkün olan bütün birləşmələri sınamağı və sonra target_sum-a aparanların qısa siyahısını daxil etməyi əhatə edir.

  • Buradakı rekursiv funksiya budur hesablamaq
  • Mümkün birləşmələri izləmək üçün qlobal dəyişən sayını saxlayırıq
  • Hər dəfə yeni bir mövqeyimiz var. Yoxlayırıq:
    • Əgər pos <= massivin uzunluğu
      • İndiyə qədər cəm hədəfə bərabərdirsə
        • artım sayı
      • Cəmi hədəfə bərabər deyilsə
        • geri qayıt (seqmentasiya xətası istəmirsiniz yoxsa yox?)
    • Hər dəfə zəng etdikdə növbəti mövqe üçün hesablayın
      • Növbəti elementi cəminə əlavə edirik
        • Beləliklə, “+” istifadə etmək
      • Cəmdən növbəti elementi çıxardırıq
  • Beləliklə, “-” istifadə etmək

Artıq prosesə ümumi baxdığımıza görə kodu yazaq

Hədəf Cəmi üçün Java Kodu

class Solution
{
    int count=0;
    public void calculate(int[]nums,int pos,int sum,int S)
    {
        if(pos==nums.length)
        {
        if(sum==S)
            count++;
        return;
        }
        calculate(nums,pos+1,sum+nums[pos],S);
        calculate(nums,pos+1,sum-nums[pos],S);   
    }
    public int findTargetSumWays(int[] nums, int S) 
    {
        calculate(nums,0,0,S);
        return count;
    }
}

Hədəf Cəmi üçün C ++ Kodu

class Solution 
{
public:
    int count=0;
public:
    void calculate(vector<int>& nums,int pos,int sum,int S)
    {
        if(pos==nums.size())
        {
        if(sum==S)
            count++;
        return;
        }
        calculate(nums,pos+1,sum+nums[pos],S);
        calculate(nums,pos+1,sum-nums[pos],S);   
    }
public:
    int findTargetSumWays(vector<int>& nums, int S)
    {
       calculate(nums,0,0,S);
       return count;
    }
};

Mürəkkəblik təhlili

Zaman Mürəkkəbliyi = O (2 ^ n)

Niyə? = Rekursiya ağacının ölçüsü (2 ^ n) x (n)

Yanaşma-2

Hədəf məbləğini tapmaq üçün dinamik proqramlaşdırma

  • Bir sıra Dp yaradın
  • Dp [i] [j] = I elementləri ilə cəminə çatmağın sayı
  • Dizini doldurarkən iki şeyi yoxlayırıq
    • Element + əvvəlki elementlərdən cəmi <2 * cəmi
      • Növbəti elementi əlavə etmək üçün kifayət qədər təhlükəsizik
      • Beləliklə Dp [i] [j] = Dp [i-1] [j] + Dp [i-1] [j + nums [i-1]]
      • Beləliklə “+” ilə birləşən bir kombinasiya əldə edirik.
    • Əvvəlki elementlərdən element cəmi> = 0
      • Növbəti elementi çıxarmaq üçün kifayət qədər təhlükəsizik
      • Beləliklə Dp [i] [j] = Dp [i-1] [j] -Dp [i-1] [j + nums [i-1]] Hədəf_sumunu tapmaq üçün
      • İndi “-” ilə əlaqəli bir birləşmədir
  • Dp [sum + Hədəf] qayıdın
    • Niyə?
    • Aralıq -sumdan + sum-a qədər dəyişir

Sözügedən hal üçün bir diaqramla prosesi izah etmək

Nümunə sıra üçün hədəf cəmi tapmaqPin
Verilən problem üçün DP seriyası narıncı, qırmızı və yaşıl rənglərlə vurğulanır

Təsvir üçün açar

  • Yaşıl-0 dəyərləri
  • Narıncı-Sıfır dəyərlər
  • Qırmızı cavab

Kodlaşdırma hissəsinə gələk

Hədəf Cəmi üçün Java Kodu

class Solution 
{
    public int findTargetSumWays(int[] nums, int S) 
    {
    int sum=0;
    for(int i=0;i<nums.length;i++)
        sum=sum+nums[i];
    if (S<-sum || S>sum) 
        return 0;
    int dp[][]=new int[nums.length+1][sum*2+1];
    dp[0][sum]=1;
    for(int i=1;i<=nums.length;i++)
    {
        for(int j=0;j<sum*2+1;j++)
        {
            if(j+nums[i-1]<sum*2+1)
                dp[i][j]=dp[i][j]+dp[i-1][j+nums[i-1]];
            if(j-nums[i-1]>=0)
                dp[i][j]=dp[i][j]+dp[i-1][j-nums[i-1]];
        }
    }
    return dp[nums.length][sum+S];
    }
}

Hədəf Cəmi üçün C ++ Kodu

class Solution 
{
public:
    int findTargetSumWays(vector<int>& nums, int S) 
    {
    int sum=0;
    for(int i=0;i<nums.size();i++)
        sum=sum+nums[i];
    if (S<-sum || S>sum) 
        return 0;
    vector<vector<int>> dp(nums.size() + 1, vector<int>(sum*2 + 1, 0));
    //int dp[nums.size()+1][sum*2+1];
    dp[0][sum]=1;
    for(int i=1;i<=nums.size();i++)
    {
        for(int j=0;j<sum*2+1;j++)
        {
            if(j+nums[i-1]<sum*2+1)
                dp[i][j]=dp[i][j]+dp[i-1][j+nums[i-1]];
            if(j-nums[i-1]>=0)
                dp[i][j]=dp[i][j]+dp[i-1][j-nums[i-1]];
        }
    }
    return dp[nums.size()][sum+S];    
    }
};

Mürəkkəblik təhlili

Zaman Mürəkkəbliyi = O (n * cəm)

Kosmik Mürəkkəblik = O (n ^ 2)

References

Translate »