给定长度的序列,其中每个元素大于或等于前一个的两倍


难度级别 易得奖学金
经常问 Accenture 亚马逊 编码国家 Facebook 谷歌 贝宝 高通公司
分而治之 动态编程

问题“给定长度的序列,其中每个元素大于或等于前一个的两倍”为我们提供了两个整数m和n。 这里 m 是序列中可以存在的最大数字,并且 是必须按要求的顺序出现的元素数。 序列上还有一个条件,即每个元素应大于或等于前一个元素的两倍。 找出满足所有条件的序列总数。

使用案列

n = 3, m = 6
4

说明

在给定条件下可以创建4个序列:(1、2、4),(1、2、5),(1、2、6),(1、3、6)。

途径

这个问题要求我们找到给定长度的序列总数,其中每个元素都大于或等于前一个的两倍。 具有高时间复杂度的天真的解决方案可以是生成所有长度的序列 n. 元素应遵循升序,并且最大数量不得超过 m. 但是,如果我们合并一个事实,那就是每个元素都应该大于或等于前一个元素的两倍,这可能是一个更有效的解决方案。 因此,我们可以编写一个递归公式。 如果我们选择 那么我们必须找到具有长度的序列 正1 和最大元素 m / 2。 否则,我们需要找到具有长度的序列 和最大元素 M-1。 即使这种方法比前面讨论的方法更有效。 这也是费时的。

给定长度的序列,其中每个元素大于或等于前一个的两倍

在确实有递归公式的情况下,我们使用 动态编程。 我们将简单地记住以上内容 递归 我们讨论过的解决方案。 在这种情况下,我们有2个状态。 第一个是最大数目,另一个是序列的长度。

代码

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表来存储中间结果。 空间复杂度也是多项式。