计算所有乘积小于K的子序列  


难度级别 易得奖学金
经常问 ByteDance Capital One公司 编码国家 Databricks 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问题,我们有两种状态,一种是到目前为止的乘积,第二种是输入数组的索引。 我们从产品开始,检查是否可以从输入数组中获得带有数字/元素的所需结果。

参见
最多69个数字的Leetcode解决方案

我们的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

复杂度分析  

时间复杂度

O(N * K), 因为存在两种状态,一种是输入数组的索引,另一种是子序列限制的乘积。 它们具有上限N和K,因此时间复杂度是多项式。

空间复杂度

O(N * K), 因为我们创建了带有N * K个单元格的2D DP表。 因此,空间复杂度也是多项式。

参见
二项式系数