모든 요소가 이전의 두 배 이상인 주어진 길이의 시퀀스  


난이도 쉽게
자주 묻는 질문 Accenture 아마존 코드네이션 페이스북 서비스 구글 페이팔 퀄컴
분열과 정복 동적 프로그래밍

"모든 요소가 이전의 두 배 이상인 주어진 길이의 시퀀스"문제는 두 개의 정수 m과 n을 제공합니다. 여기 m 시퀀스에 존재할 수있는 가장 큰 숫자이며 필수 시퀀스에 있어야하는 요소의 수입니다. 시퀀스에 부과되는 조건이 하나 더 있습니다. 즉, 각 요소는 이전 요소보다 두 배 이상이어야합니다. 모든 조건이 충족되는 총 시퀀스 수를 찾으십시오.

예  

n = 3, m = 6
4

설명

주어진 조건에서 만들 수있는 4 개의 시퀀스가 ​​있습니다 : (1, 2, 4), (1, 2, 5), (1, 2, 6), (1, 3, 6).

접근  

문제는 모든 요소가 이전의 두 배 이상인 주어진 길이의 총 시퀀스 수를 찾도록 요청합니다. 시간 복잡도가 높은 순진한 솔루션은 모든 길이 시퀀스를 생성 할 수 있습니다. n. 요소는 오름차순을 따라야하며 최대 수는 m. 그러나 각 요소가 이전 요소보다 두 배 이상이어야한다는 사실을 통합하면 더 효율적인 솔루션이 될 수 있습니다. 따라서 우리는 재귀 공식을 작성할 수 있습니다. 우리가 선택하면 길이가있는 시퀀스를 찾아야합니다. n-1 및 최대 요소 m / xnumx. 그렇지 않으면 길이가있는 시퀀스를 찾아야합니다. 및 최대 요소 m-1. 이 접근 방식은 이전에 논의한 접근 방식보다 약간 더 효율적이지만. 이것은 또한 시간이 많이 걸립니다.

참조
하위 배열이 산의 형태인지 확인

모든 요소가 이전의 두 배 이상인 주어진 길이의 시퀀스

재귀 공식이있는 경우에는 동적 프로그래밍. 위의 내용을 간단히 메모하겠습니다. 재귀 우리가 논의한 솔루션. 이 경우 두 가지 상태가 있습니다. 첫 번째는 최대 수이고 다른 하나는 시퀀스의 길이입니다.

암호  

모든 요소가 이전의 두 배 이상인 주어진 길이의 시퀀스를 찾는 C ++ 코드

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n = 3, m = 6;
    int dp[m+1][n+1];
    memset(dp, 0, sizeof dp);
    for(int i=0;i<=m;i++)
        dp[i][0] = 1;
    int ans = 0;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            // we pick the current element
            dp[i][j] = dp[i/2][j-1];
            // we ignore the current element
            dp[i][j] += dp[i-1][j];
        }
    }
    cout<<dp[n][m];
}
4

모든 요소가 이전의 두 배 이상인 주어진 길이의 시퀀스를 찾는 Java 코드

import java.util.*;
class Main{
  public static void main(String[] args)
  {
      int n = 3, m = 6;
      int dp[][] = new int[m+1][n+1];
      for(int i=0;i<=n;i++)
      	for(int j=0;j<=m;j++)
      		dp[i][j] = 0;
      for(int i=0;i<=m;i++)
          dp[i][0] = 1;
      for(int i=1;i<=m;i++){
          for(int j=1;j<=n;j++){
              // we pick the current element
              dp[i][j] = dp[i/2][j-1];
              // we ignore the current element
              dp[i][j] += dp[i-1][j];
          }
      };
    System.out.print("dp[n][m]");
  }
}
4

복잡성 분석  

시간 복잡성

O (N * M), 문제의 상태는 시퀀스의 길이와 고려할 수있는 최대 수이기 때문입니다. 따라서 시간 복잡도는 다항식입니다.

공간 복잡성

O (N * M), 중간 결과를 저장하기 위해 2D DP 테이블을 만들었 기 때문입니다. 공간 복잡성도 다항식입니다.