1, 2 же 3-кадамды колдонуп, n-тепкичке жетүү жолдорун эсептеңиз


Кыйынчылык деңгээли жеңил
Көп суралган Amazon CodeNation GE Саламаттыкты сактоо Microsoft Moonfrog Labs 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-тепкичке чыгуунун жолдорун санап беришибиз керек.

Бардык ыкмаларды жаратып, андан кийин аларды эсептеп чыгуу - жөнөкөй мамиле. Бирок мындай ыкма көп убакытты талап кылат. Ошентип, убакыттын татаалдыгын азайтуу үчүн биз ар кандай жолдорду ойлонушубуз керек. Биз жөнөкөй эмес мамиледе талкуулаган метод а рекурсивдүү 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 массивин түзүшүбүз керек. Чечимдин космостук татаалдыгы сызыктуу.