时间戳

首页 > 解决方案 > 查找具有连续差 = k 的数组中的子序列总数

javascript - 查找具有连续差 = k 的数组中的子序列总数

问题描述

在给定的数组中，我试图找到子序列的总数，例如：

例如，在数组:[10,13,7,8,14,200, 876, 11]中，它有 5 个遵循上述条件的子序列。

我正在尝试一种自下而上的方法。我尝试了以下方法，但它没有给出所有子序列并输出 4 而不是 5。

我该如何处理？我有一种直觉，该方法可能类似于最长递增子序列，但不确定如何。

标签： javascriptarraysalgorithmdynamic-programmingsubsequence

解决方案

令 f(i) 为满足以下条件的子序列数：

  • 从 A[0] 开始
  • 以 A[i] 结束
  • 连续词之间的差异不大于3

那么问题的答案将是 f(A.length()-1)。

以下是 C++ 自下而上的代码：

int A[] = {10,13,7,8,14,11};
int f[6];
int n = 6;
    
for (int i=0;i<n;i++) f[i] = 0;
f[0]=1;
for (int i=1;i<n;i++){
  for (int j=0;j<i;j++){
     if (abss(A[i] - A[j]) <= 3)
         f[i] += f[j];
  }
}
cout<<f[n-1]<<endl;//printing the result

这是用 C++ 自上而下的方法编写的代码：

int A[] = {10,13,7,8,14,11};
int n = 6;

int memo[6];//initialized with -1s;

int count(int currIndex){
  if (currIndex == n-1) return 1;
  if (memo[currIndex] != -1) return memo[currIndex];
  
  int res = 0;
  for (int i=currIndex+1 ; i<n ; i++){
      if (abss(A[currIndex] - A[i]) <= 3){
            res += count(i);
      }
  }
    
  memo[currIndex] = res;
  return res;
}

结果将是在第一个索引处调用 count ，如下所示：

count(0);

推荐阅读