Հաշվեք K- ից պակաս արտադրյալ ունեցող բոլոր հետևյալները


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են ByteDance Capital One CodeNation Տվյալների շտեմարաններ Expedia Yandex
Դասավորություն Դինամիկ ծրագրավորում

«Հաշվեք բոլոր հաջորդականությունները, որոնք ունեն K- ից պակաս արտադրանք» խնդրի համաձայն `ձեզ տրվում է ամբողջ թվերի զանգված: Այժմ գտեք ենթադասերի քանակը, որոնք ունեն արտադրանք ավելի քիչ, քան տրված մուտքային K- ն:

Օրինակ

Հաշվեք K- ից պակաս արտադրյալ ունեցող բոլոր հետևյալները

a[] = {1, 2, 3, 4, 5}
k = 8
Number of subsequences less than 8: 11

բացատրություն

Գոյություն ունեն 11 հաջորդականություններ, որոնց արտադրյալն ավելի քիչ է, քան տրված k- ն (= 8): Հետևյալները ներկայացված են վերևում նկարում:

Մոտեցում

Խնդիրը մեզ ապահովեց ամբողջ թվերի հաջորդականություն և ամբողջ թիվ K., ապա մեզ ասացին, որ գտնելու ենք ենթադասերի քանակը, որոնց արտադրյալը պակաս է K- ից: Ուստի, երբ գործ ունենք հետևյալների, ենթաբազմությունների կամ ենթածրագրերի հետ: Միամիտ մոտեցում է միշտ առաջացնել այս հաջորդականությունները և այնուհետև ստուգել, ​​թե արդյոք առաջացած հաջորդականությունը բավարարում է մեր պայմաններին, թե ոչ:

Այս միամիտ լուծումը, անշուշտ, կգերազանցի մեր ժամկետը: Այսպիսով, խնդիրը լուծելու համար տրված ժամանակային սահմանափակումով: Մեզանից պահանջվում է օգտագործել Դինամիկ ծրագրավորում, Այսպիսով, այստեղ մենք կանցնենք մուտքային զանգվածի վրայով: Անցման ընթացքում մենք միաժամանակ կլրացնենք DP աղյուսակը: Այս DP խնդրի համար մենք ունենք երկու վիճակ. Առաջինը արտադրանքն է մինչ այժմ և երկրորդը `մուտքային զանգվածի ինդեքսը: Մենք սկսում ենք արտադրանքից և ստուգում ենք, արդյոք կարող ենք մուտքային զանգվածից թվեր / տարրերով պահանջվող արդյունքը ստանալ:

Մեր dp զանգվածի dp [i] [j] նշանակում է հետևյալների քանակը, որոնք ունեն արդյունք պակաս i- ից և կազմվում են մուտքի առաջին j տարրերի օգտագործմամբ: Այսպիսով, dp [i] [j] գտնելու համար մենք կախված ենք dp [i / a [j]] [j] և dp [i] [j-1]: Այսպիսով, եթե a [i]> i, այս տարրը հետևյալի մեջ վերցնելը կնշանակի, որ a [i] ինքնին ավելի մեծ է, քան K. Այսպիսով, այս տարրը չի դիտարկվի: Այսպիսով, մենք այդպես ենք հաշվում K- ից պակաս արդյունք ունեցող բոլոր հետևյալները:

Կոդ

C ++ կոդ ՝ K- ից պակաս արտադրանք ունեցող բոլոր հետևյալները հաշվելու համար

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

int main(){
    int a[] = {1, 2, 3, 4, 5};
    int n = (sizeof a)/(sizeof a[0]);
    int k = 8;
    int dp[k][n+1];
    memset(dp, 0, sizeof(dp));

    for (int i=1;i<k;i++){
        for (int j=1;j<=n;j++){
            dp[i][j] = dp[i][j-1];
            if (a[j-1] <= i && a[j-1] > 0)
                dp[i][j] += dp[i/a[j-1]][j-1] + 1;
        }
    }

    cout<<dp[k-1][n];
}
11

Java կոդ ՝ K- ից պակաս արտադրանք ունեցող բոլոր հետևյալները հաշվելու համար

import java.util.*;
class Main{
  public static void main(String[] args)
  {
      int a[] = {1, 2, 3, 4, 5};
      int n = a.length;
      int k = 8;
      int dp[][] = new int[k][n+1];
      for(int i=0;i<k;i++)
      	for(int j=0;j<n+1;j++)
      		dp[i][j] = 0;

      for (int i=1;i<k;i++){
          for (int j=1;j<=n;j++){
              dp[i][j] = dp[i][j-1];
              if (a[j-1] <= i && a[j-1] > 0)
                  dp[i][j] += dp[i/a[j-1]][j-1] + 1;
          }
      }
    System.out.println(dp[k-1][n]);
  }
}
11

Բարդության վերլուծություն

Timeամանակի բարդություն

O (N * K), քանի որ կա երկու վիճակ, մեկը մուտքային զանգվածի ցուցիչն է, իսկ մյուսը ՝ հետևյալ սահմանաչափի արտադրանքը: Նրանք ունեն N և K վերին սահմաններ, ուստի ժամանակի բարդությունը բազմանդամ է:

Տիեզերական բարդություն

O (N * K), քանի որ մենք ստեղծեցինք 2D DP աղյուսակ N * K բջիջներով: Այսպիսով, տիեզերական բարդությունը նույնպես բազմանդամ է: