Пребройте всички подпоследователности, които имат продукт по-малък от K


Ниво на трудност Лесно
Често задавани в ByteDance Capital One CodeNation Databricks Expedia Yandex
Array Динамично програмиране

Проблемът „Преброяване на всички подпоследователности с произведение по-малко от 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, приемането на този елемент в подпоследователността ще означава, че самият [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

Анализ на сложността

Сложност във времето

O (N * K), защото има две състояния, едното е индексът за входния масив, а другото е произведение на ограничението на подпоследователността. Те имат горна граница N и K, поради което сложността на времето е полиномна.

Сложност на пространството

O (N * K), защото създадохме 2D DP таблица с N * K клетки. По този начин сложността на пространството също е многочленна.