Μετρήστε όλες τις ακολουθίες με προϊόν μικρότερο από K


Επίπεδο δυσκολίας Εύκολος
Συχνές ερωτήσεις ByteDance Capital One CodeNation Βάσεις δεδομένων Expedia Yandex
Παράταξη Δυναμικός προγραμματισμός

Το πρόβλημα "Μετρήστε όλες τις ακολουθίες με προϊόν μικρότερο από K" δηλώνει ότι σας δίνεται μια σειρά από ακέραιους αριθμούς. Τώρα βρείτε τον αριθμό των ακολουθιών που έχουν ένα προϊόν μικρότερο από μια δεδομένη είσοδο Κ.

Παράδειγμα

Μετρήστε όλες τις ακολουθίες με προϊόν μικρότερο από K

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

εξήγηση

Υπάρχουν 11 ακολουθίες που έχουν προϊόν μικρότερο από το δεδομένο k (= 8). Οι ακολουθίες φαίνονται στην παραπάνω εικόνα.

Προσέγγιση

Το πρόβλημα μας παρείχε μια ακολουθία ακέραιων αριθμών και έναν ακέραιο Κ. Τότε μας λένε να βρούμε τον αριθμό των ακολουθιών που έχουν ένα προϊόν μικρότερο από το Κ. Έτσι, όποτε ασχολούμαστε με μεταγενέστερα, υποσύνολα ή subarrays. Μια αφελής προσέγγιση είναι πάντα η δημιουργία αυτών των ακολουθιών και, στη συνέχεια, ελέγξτε αν η παραγόμενη ακολουθία ικανοποιεί τις συνθήκες μας ή όχι;

Αυτή η αφελής λύση σίγουρα θα ξεπεράσει το χρονικό μας όριο. Έτσι, για να λυθεί το πρόβλημα κάτω από το δεδομένο χρονικό περιορισμό. Πρέπει να χρησιμοποιήσουμε Δυναμικός προγραμματισμός. Εδώ λοιπόν θα διασχίσουμε τον πίνακα εισόδου. Κατά τη διάρκεια της διέλευσης, θα γεμίσουμε ταυτόχρονα τον πίνακα DP. Έχουμε δύο καταστάσεις για αυτό το πρόβλημα DP, το πρώτο είναι το προϊόν μέχρι τώρα και το δεύτερο είναι το ευρετήριο για τον πίνακα εισαγωγής. Ξεκινάμε με το προϊόν και ελέγχουμε εάν μπορούμε να πάρουμε το απαιτούμενο αποτέλεσμα με τους αριθμούς / στοιχεία από τον πίνακα εισαγωγής.

Το κελί dp array dp [i] [j] υποδηλώνει τον αριθμό των ακολουθιών που έχουν προϊόν μικρότερο από το i και σχηματίζονται χρησιμοποιώντας τα πρώτα στοιχεία j της εισόδου. Έτσι, για την εύρεση dp [i] [j], εξαρτώνται από το dp [i / a [j]] [j] και το dp [i] [j-1]. Επομένως, εάν ένα [i]> i, η εισαγωγή αυτού του στοιχείου στη συνέχεια θα σημαίνει ότι το [i] το ίδιο είναι μεγαλύτερο από το 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

Ανάλυση πολυπλοκότητας

Χρόνος πολυπλοκότητας

Ο (Ν * Κ), επειδή υπάρχουν δύο καταστάσεις η μία είναι το ευρετήριο για τον πίνακα εισαγωγής και η άλλη είναι το προϊόν του ορίου μεταγενέστερης. Έχουν ένα άνω όριο Ν και Κ, επομένως η πολυπλοκότητα του χρόνου είναι πολυώνυμη.

Διαστημική πολυπλοκότητα

Ο (Ν * Κ), γιατί δημιουργήσαμε έναν πίνακα 2D DP με κελιά N * K. Έτσι, η διαστημική πολυπλοκότητα είναι επίσης πολυώνυμη.