제품이 K 미만인 모든 하위 시퀀스를 계산합니다.

난이도 쉽게
자주 묻는 질문 ByteDance 자본 하나 코드네이션 데이터 브릭 Expedia Yandex 주차
배열 동적 프로그래밍조회수 32

"K보다 작은 곱을 갖는 모든 하위 시퀀스 계산"문제는 정수 배열이 제공된다는 것을 나타냅니다. 이제 주어진 입력 K보다 작은 곱을 갖는 하위 시퀀스의 수를 찾으십시오.

제품이 K 미만인 모든 하위 시퀀스를 계산합니다.

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

설명

주어진 k (= 11)보다 작은 곱을 갖는 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보다 작은 곱을 갖는 모든 하위 시퀀스를 계산하는 방법입니다.

암호

제품이 K 미만인 모든 하위 시퀀스를 계산하는 C ++ 코드

#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

제품이 K 미만인 모든 하위 시퀀스를 계산하는 Java 코드

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 테이블을 만들었 기 때문입니다. 따라서 공간 복잡성도 다항식입니다.

Translate »