Решение за лек-код на Паскал Триаголник II


Ниво на тешкотија Лесно
Често прашувано во Амазон Мајкрософт
Низа Динамичко програмирање Математика

Содржина

Изјава за проблем

Во овој проблем ни е даден Индексот на редови (i) од Паскалскиот триаголник. Треба да создадеме линеарна низа што ги содржи вредностите на јетиот ред и да ја вратиме. Индексот на редови започнува од 0.
Знаеме дека триаголникот на Паскал е триаголник каде секој број е збир на двата броја директно над него.

Решение за лек-код на Паскал Триаголник II

пример

rowIndex = 3
[1,3,3,1]
rowIndex = 0
[1]

Како што знаеме дека секоја вредност во паскаловиот триаголник е биномен коефициент (nCr) каде што n е редот и r е индексот на колоната на таа вредност.

Дискутиравме за сличен проблем кога треба да ги вратиме сите редови од индексот на редови 0 во дадениот индекс на редови на паскаловиот триаголник тука - Ласка код на Паскал триаголник

Но, во овој проблем треба да вратиме само еден ред чиј индекс е даден.
Тука ќе разговараме за три пристапи за решавање на овој проблем:

Пристап 1 (Рекурзија на брутална сила)

Знаеме дека секој број во овој триаголник е збир на двата броја директно над него. т.е.
Num (ред, коло) = Num (ред-1, коло) + Num (ред-1, коло-1).
Значи, можеме постојано да ја повикуваме функцијата Num (rowIndex, j) за секој индекс на колони од тој ред и да ја вратиме формираната листа.

Како што можеме да видиме, имаме формулирано рекурзивен пристап за наоѓање на Num (i, j). Сега постојат неколку основни случаи за тоа што се:

  • Вредноста на првиот ред ќе биде 1. Значи, за редот = 0, Број (ред,…) = 0.
  • Вредноста на првата колона ќе биде 1. Значи, за коло = 0, Број (…, коло) = 0.
  • Последната вредност на секој ред ќе биде еднаква на 1. Значи, за коло = ред = k, Num (k, k) = 0.

Имплементација на решението за лек код на Паскал Триаголник II

Програма C ++

#include <bits/stdc++.h>
using namespace std;

int nCr(int n,int r)
{
    if(n==0 || r==0 || r==n)
        return 1;

    return nCr(n-1,r-1)+ nCr(n-1,r);
}


vector<int> getRow(int rowIndex) 
{
    vector<int> res(rowIndex+1);

    for(int i=0;i<=rowIndex;i++)
        res[i]= nCr(rowIndex,i);

    return res;

}

int main() 
{
    int rowIndex=3;
    vector<int> ans= getRow(rowIndex);
    for(auto val:ans) cout<<val<<" ";
    
    cout<<endl;
    return 0; 
}
1 3 3 1

Програма за Java

import java.util.*;

class Rextester{
    
    static int nCr(int n,int r)
    {
        if(n==0 || r==0 || r==n)
            return 1;

        return nCr(n-1,r-1)+ nCr(n-1,r);
    }

    public static List<Integer> getRow(int rowIndex) 
    {
       List<Integer> res=new ArrayList<Integer>();
        for(int i=0;i<=rowIndex;i++)
            res.add(nCr(rowIndex,i));

        return res;
    }

  public static void main(String args[])
    {
       	int rowIndex=3;
        List<Integer> ans= getRow(rowIndex);
        for(int val:ans)  System.out.print(val+" ");
    }
}
1 3 3 1

Анализа на сложеност за решението со лек код на Паскал Триаголник II

Временска комплексност

О (2 ^ к): каде k е даден индекс на редови.
Ние ја нарекуваме рекурзијата за Num (i, j) како Num (i-1, j) + Num (i-1, j-1). Оттука, времето за наоѓање на Num (n, r) ќе биде nCr.
Ја повикуваме оваа рекурзивна функција за целиот индекс на колони од дадениот ред (k) .ie
kC0 + kC1 + kC2 +. + kCk = 2 ^ k.
Оттука, вкупната временска сложеност ќе биде O (2 ^ k).

Комплексноста на просторот 

Добро): Потребен ни е простор О (к) за да ги зачуваме сите вредности на дадениот ред во списокот. Исто така, во најлош случај, на нашата рекурзија ќе ни треба О (k) магацин за рекурзивен повик. Оттука O (k) + O (k) = ~ O (k).

Пристап 2 (Динамичко програмирање)

Во горната рекурзија можеме да видиме дека постојано ја повикуваме функцијата Num (i, j) за истата (i, j).

Значи, она што можеме да го направиме е дека можеме да ги меморираме ансите за секое (i, j) така што секогаш кога ќе има потреба повторно да ја повикуваме таа функција, да го вратиме кешираниот одговор директно од меморијата без повторно да пресметаме. Така заштедувате многу време.
За динамично складирање на одговорите што можеме да ги користиме хаш-мапа каде клуч ќе биде комбинацијата на индексот на редови и индексот на колоната.

Уште нешто што можеме да видиме тука е дека ни требаат само претходни вредности на редот за наоѓање на вредностите на тековниот ред. Затоа, можеме да зачуваме само една вредност на редот истовремено и да го користиме за да ги најдеме вредностите на следниот ред. Оттука, тука можеме да ја намалиме комплексноста на вселената на O (k).

Алгоритам за оптимизација на просторот:
1. Создадете две низи соодветно за претходниот ред и тековниот ред.
2. Иницијализирање Претходна ред како {1}.
3. Извршете јамка за ith ред од i = 1 до i =rowIndex. И генерирајте нови вредности на редови од претходниот ред и зачувајте ги во curr низа
4. Сега ажурирајте Претходна ред со доделување мом ред до Претходна ред и повторете го истиот процес во оваа јамка.
5. Вратете го последниот ред зачуван во Претходна низа

Имплементација на решението за лек код на Паскал Триаголник II

Програма C ++ со употреба на мемоизација

#include <bits/stdc++.h>
using namespace std;

unordered_map<string,int> cache;

int nCr(int n,int r)
{
    string key= to_string(n)+to_string(r);
    if(cache.count(key)) return cache[key]; 

    if(n==0 || r==0 || r==n)
        return 1;

    return ( cache[key]= nCr(n-1,r-1)+ nCr(n-1,r) );
}


vector<int> getRow(int rowIndex) 
{
    vector<int> res(rowIndex+1);

    for(int i=0;i<=rowIndex;i++)
        res[i]= nCr(rowIndex,i);

    return res;

}

int main() 
{
    int rowIndex=3;
    vector<int> ans= getRow(rowIndex);
    for(auto val:ans) cout<<val<<" ";
    
    cout<<endl;
    return 0; 
}

Програма C ++ (оптимизиран простор за простор)

#include <bits/stdc++.h>
using namespace std;

vector<int> getRow(int rowIndex) 
{
    vector<int> prev={1},curr;
    for(int i=1;i<=rowIndex;i++)
    {
        curr.clear();
        curr.resize(i+1,1);

        for(int j=1;j<i;j++)
            curr[j]=prev[j]+prev[j-1];

        prev=curr;
    }

    return prev;
}

int main() 
{
    int rowIndex=3;
    vector<int> ans= getRow(rowIndex);
    for(auto val:ans) cout<<val<<" ";
    
    cout<<endl;
    return 0; 
}
1 3 3 1

Јава програма со употреба на меморирање

import java.util.*;

class Rextester{
    
    static Map<String,Integer> cache=new HashMap<String,Integer>();
    
    static int nCr(int n,int r)
    {
        String key= "" + n + r;
        if(cache.containsKey(key)) return cache.get(key); 
        
        if(n==0 || r==0 || r==n)
            return 1;
        
        int ans= nCr(n-1,r-1)+ nCr(n-1,r);
        cache.put(key,ans);
        return ans;
    }

    public static List<Integer> getRow(int rowIndex) 
    {
       List<Integer> res=new ArrayList<Integer>();
        for(int i=0;i<=rowIndex;i++)
            res.add(nCr(rowIndex,i));

        return res;
    }

  public static void main(String args[])
    {
       	int rowIndex=3;
        List<Integer> ans= getRow(rowIndex);
        for(int val:ans)  System.out.print(val+" ");
    }
}

Java програма (оптимизиран простор за ДП)

#include <bits/stdc++.h>
using namespace std;

vector<int> getRow(int rowIndex) 
{
    vector<int> prev={1},curr;
    for(int i=1;i<=rowIndex;i++)
    {
        curr.clear();
        curr.resize(i+1,1);

        for(int j=1;j<i;j++)
            curr[j]=prev[j]+prev[j-1];

        prev=curr;
    }

    return prev;
}

int main() 
{
    int rowIndex=3;
    vector<int> ans= getRow(rowIndex);
    for(auto val:ans) cout<<val<<" ";
    
    cout<<endl;
    return 0; 
}
1 3 3 1

Анализа на сложеност за решението со лек код на Паскал Триаголник II

Временска комплексност

О (к ^ 2):  Мемоизацијата ќе осигури дека одреден елемент се пресметува само еднаш. И под претпоставка дека е потребно постојано време за да се извлечат ans од хаш-мапа, потребно е постојано време да се пресмета секоја вредност на триаголникот на Паскал.
Сега на крајот пресметуваме 1 + 2 + 3 +… + (k + 1) = (k + 1) (k + 2) / 2 вредности што е = ~ O (k ^ 2).

Комплексноста на просторот 

1. Едноставното меморирање би ги држело сите 1 + 2 + 3 +… + (k + 1) = (k + 1) (k + 2) / 2 елементи во најлош случај. Тоа би барало О (к ^ 2) простор.
2. Во вселенски оптимизиран ДП ни треба Добро) простор само за складирање на најновиот генериран ред.

Пристап 3 (математика)

Како што знаеме дека секоја вредност во паскаловиот триаголник е биномен коефициент (nCr). И можеме да напишеме nCr како:
Решение за лек-код на Паскал Триаголник II

Сега, ако забележиме, последователните биномски коефициенти nC (r-1) и nCr се разликуваат според факторот на:
Решение за лек-код на Паскал Триаголник II

Така, можеме да го изведеме следниот поим по ред во триаголникот на Паскал, од претходниот израз.

Алгоритам:

  1. Иницијализирајте го првиот термин од редот како 1.
  2. Извршете јамка за индексирана колона и пресметајте го следниот термин (термин (i)) како термин (i) = термин (i-1) * (n-i + 1) / i.
  3. Вратете ги пресметаните вредности како список.

Имплементација на решението за лек код на Паскал Триаголник II

Програма C ++

#include <bits/stdc++.h>
using namespace std;

vector<int> getRow(int rowIndex) 
{
    int n=rowIndex;
   vector<int> res;
   res.push_back(1);

    for(int i=1;i<=n;i++)
    {
       int x= (int) ( ((long long)res.back()*(n-i+1) ) /i);
       res.push_back(x);
    }

    return res;
}

int main() 
{
    int rowIndex=3;
    vector<int> ans= getRow(rowIndex);
    for(auto val:ans) cout<<val<<" ";
    
    cout<<endl;
    return 0; 
}
1 3 3 1

Програма за Java

import java.util.*;

class Rextester{

    public static List<Integer> getRow(int rowIndex) 
    {
       int n=rowIndex;
       List<Integer> res=new ArrayList<Integer>();
       res.add(1);
        
        for(int i=1;i<=n;i++)
        {
           int x= (int) ( ((long)res.get(res.size()-1)*(n-i+1) ) /i);
           res.add(x);
        }
        
        return res;
    }

  public static void main(String args[])
    {
       	int rowIndex=3;
        List<Integer> ans= getRow(rowIndex);
        for(int val:ans)  System.out.print(val+" ");
    }
}
1 3 3 1

Анализа на сложеност за решението со лек код на Паскал Триаголник II

Временска комплексност

Добро): Секоја вредност на редот се пресметува во постојано време.

Комплексноста на просторот 

Добро): Не е потребен дополнителен простор освен за задржување на излезот.