Роҳҳои расидан ба зинапояи нумро бо истифода аз қадамҳои 1, 2 ё 3 ҳисоб кунед  


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад Amazon CodeNation GE Тандурустӣ Microsoft Озмоишгоҳҳои Moonfrog PayPal Uber
Комбинаторӣ Барномарезии динамикӣ

Масъалаи "Роҳҳои расидан ба зинапояи нумро бо истифода аз қадамҳои 1, 2 ё 3 ҳисоб кунед" мегӯяд, ки шумо дар замин истодаед. Акнун ба шумо лозим аст, ки ба охири зинапоя расед. Пас, агар шумо танҳо 1, 2 ё 3 зина ҷаҳида тавонед, чанд роҳ барои расидан ба охир вуҷуд дорад?

мисол  

Роҳҳои расидан ба зинапояи нумро бо истифода аз қадамҳои 1, 2 ё 3 ҳисоб кунед

2
2

Шарҳ

2 роҳ мавҷуд аст, зеро ё мо мустақиман аз зинаи 2-юм меравем ё аввал ба зинапояи 1 мерасем, сипас ба пеш ҳаракат мекунем.

усул  

Мушкилот аз мо шумораи умумии гуногуни роҳҳои расидан ба охири зинапояро талаб мекунад, то мо аз замин сар кунем. Пас, дида бароед, ки зинапоя дорои 2 марҳила мебошад. Пас аз он 2 роҳи имконпазир мавҷуд аст, ё шумо мустақиман ба зинаи 2 қадам мегузоред ё қадами аввал ба қадами 1 ва сипас ба зинаи 2. Ба ин монанд, мо бояд роҳҳои расидан ба зинапояи нумро бо истифода аз қадамҳои 1, 2 ё 3 ҳисоб кунем.

Равиши соддалавҳона ин тавлиди ҳама роҳҳои имконпазир ва пас ҳисоб кардани онҳост. Аммо ин равиш вақтро талаб мекунад. Ҳамин тариқ, барои кам кардани мураккабии вақт мо бояд якчанд роҳҳои гуногунро фикр кунем. Усуле, ки мо дар муносибати соддалавҳона муҳокима кардем, ин аст рекурсивӣ ҳалли он, ки шумо метавонед аз қадами 0 оғоз кунед. Пас дар ҳар як занги рекурсивӣ ба қадамҳои i + 1, i + 2 ва i + 3 гузаред. Вақте ки шумо ба қадами nth расидед, ҳисобкунакро зиёд кунед. Ҳамин тавр, дар охир ҳисобкунак шумораи роҳҳои расидан ба қадами n-умро нигоҳ медорад. Аммо ин қадам боз ҳамон мушкилотро такрор мекунад. Пас, барои беҳтар кардани ин ҳалли мо истифода мебарем Барномарезии динамикӣ.

ҳамчунин нигаред
Маҳсулоти максималии пайдарпайии афзоянда

Дар ҳалли барномасозии динамикӣ мо чунин мешуморем, ки мо дар қадами ith истодаем. Пас шумораи роҳҳои расидан ба қадам аз қадами i-1, i-2 step ё i-3 мебошад. Ҳамин тариқ, ба таври расмӣ, роҳҳои [i] = роҳҳои [i-1] + роҳҳои [i-2] + роҳҳои [i-3], бо истифода аз ин формулаи рекурсивӣ. Мо мушкилоти худро ҳал хоҳем кард.

рамз  

Рамзи C ++ барои ҳисоб кардани роҳҳои расидан ба зинаи nth бо истифода аз қадамҳои 1, 2 ё 3

#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

Рамзи Java барои ҳисоб кардани роҳҳои расидан ба зинаи nth бо истифода аз қадамҳои 1, 2 ё 3

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), зеро мо бояд то зинаи nth давра иҷро кунем. Пас, дар робита бо барномасозии динамикӣ, мо як ҳолати ягона доштем, ки аз 0 то n ва арзиши гузариш O (1) мебошад. Ҳамин тавр мураккабии вақт хатӣ аст.

Мураккабии фазо

O (N), зеро мо бояд массиви 1-D DP созем. Мураккабии фазоии ҳалли хаттӣ мебошад.