1, 2, 3-р алхамыг ашиглан n шат руу хүрэх арга замыг тоол  


Хэцүү байдлын түвшин Easy
Байнга асуудаг Амазоны CodeNation GE Эрүүл мэндийн Microsoft- Moonfrog лабораторууд PayPal Uber
Нийлмэл Динамик програмчлал

"1, 2, 3-р алхамыг ашиглан n шат руу хүрэх арга замыг тоол" гэсэн асуудал таныг газар дээр зогсож байгааг харуулж байна. Одоо та шатны төгсгөлд хүрэх хэрэгтэй. Хэрэв та зөвхөн 1, 2, эсвэл 3 алхмаар үсрэх боломжтой бол төгсгөлд хүрэх хэдэн арга зам байна вэ?

Жишээ нь  

1, 2, 3-р алхамыг ашиглан n шат руу хүрэх арга замыг тоол

2
2

Тайлбар

2 арга зам байдаг, яагаад гэвэл бид 2-р алхамыг шууд газраас шууд гаргана, эсвэл эхлээд 1-р шат хүрч дараа нь урагшилна.

арга барил  

Асуудал нь биднийг газраас эхлүүлэхийн тулд шатны төгсгөлд хүрэх өөр өөр олон арга замыг биднээс асуудаг. Тиймээс шат нь 2 алхамтай болохыг анхаарч үзээрэй. Дараа нь 2 боломжит арга байна, эсвэл шууд 2-р алхам руу шилжих эсвэл эхний алхам 1-р алхам, дараа нь 2-р алхам. Үүнтэй адил бид 1, 2, 3-р алхмуудыг ашиглан n шат руу хүрэх арга замыг тоолох хэрэгтэй.

Гэнэн хандлага бол бүх боломжит аргуудыг гаргаад дараа нь тоолох явдал юм. Гэхдээ энэ арга нь цаг хугацаа их шаардах болно. Тиймээс цаг хугацааны нарийн төвөгтэй байдлыг багасгахын тулд бид янз бүрийн аргуудыг бодож олох ёстой. Бидний гэнэн хандлагын талаар ярилцсан арга бол a рецессив 0-р алхамаас эхлэх шийдэл. Дараа нь рекурсив дуудлага бүрт i + 1, i + 2, i + 3 алхам руу очно уу. N алхам руу хүрэхэд тоолуурыг нэмэгдүүлнэ. Ингэснээр эцэст нь тоолуур n алхам руу хүрэх хэд хэдэн аргыг хадгалдаг. Гэхдээ энэ алхам нь ижил асуудлуудыг дахин дахин тооцоолох болно. Тиймээс энэхүү шийдлийг оновчтой болгохын тулд бид ашигладаг Динамик програмчлал.

мөн үзнэ үү
Өсөн нэмэгдэж буй дарааллын хамгийн их бүтээгдэхүүн

Динамик програмчлалын шийдэлд бид ith алхам дээр зогсож байна гэж үздэг. Ith алхам руу хүрэх арга замуудын тоо нь i-1 алхам, i-2 алхам эсвэл i-3 алхам юм. Энэ рекурсив томъёог ашиглан албан ёсоор хэлэхэд арга зам [i] = арга зам [i-1] + арга зам [i-2] + арга зам [i-3]. Бид асуудлаа шийдэх болно.

код  

1, 2 эсвэл 3-р алхамыг ашиглан n шатаар хүрэх арга замыг тоолох C ++ код

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

int main(){
    int n;cin>>n;
    int dp[n+1];
    // base case
    dp[0] = 1;
    for(int i=1;i<=n;i++){
        dp[i] = ((i-1)>=0 ? dp[i-1] : 0) +
                ((i-2)>=0 ? dp[i-2] : 0) +
                ((i-3)>=0 ? dp[i-3] : 0);
    }
    cout<<dp[n];
}
5
13

1, 2 эсвэл 3-р алхамыг ашиглан n шатаар хүрэх арга замыг тоолох Java код

import java.util.*;
class Main{
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
  int n = sc.nextInt();
    int dp[] = new int[n+1];
    // base case
    dp[0] = 1;
    for(int i=1;i<=n;i++){
        dp[i] = ((i-1)>=0 ? dp[i-1] : 0) +
                ((i-2)>=0 ? dp[i-2] : 0) +
                ((i-3)>=0 ? dp[i-3] : 0);
    }

    System.out.print(dp[n]);
  }
}
5
13

Нарийн төвөгтэй байдлын шинжилгээ  

Цаг хугацааны нарийн төвөгтэй байдал

O (N), Учир нь бид n алхам хүртэл давталт хийх ёстой. Тиймээс Динамик програмчлалын хувьд бид 0-ээс n хооронд хэлбэлздэг нэг төлөвтэй байсан ба шилжилтийн өртөг нь O (1) байна. Тиймээс цаг хугацааны нарийн төвөгтэй байдал нь шугаман юм.

Сансрын нарийн төвөгтэй байдал

O (N), Учир нь бид 1-D DP массив үүсгэх хэрэгтэй. Уусмалын орон зайн нарийн төвөгтэй байдал нь шугаман байна.