Подсчитайте все подпоследовательности, у которых произведение меньше K


Сложный уровень Легко
Часто спрашивают в ByteDance Capital One CodeNation Databricks Expedia Яндекс
массив Динамическое программирование

Задача «Подсчитать все подпоследовательности, имеющие продукт меньше 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

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

Сложность времени

О (Н * К), потому что есть два состояния: одно - это индекс для входного массива, а другое - произведение предела подпоследовательности. У них есть верхняя граница N и K, поэтому временная сложность полиномиальна.

Космическая сложность

О (Н * К), потому что мы создали 2D-таблицу DP с N * K ячейками. Таким образом, сложность пространства также полиномиальна.