计算 Product 小于 K 的所有子序列

Question

给定一个非负数组，找出乘积小于 K 的子序列的数量。

示例：

输入：[1, 2, 3, 4] k = 10 输出：11

输入：[4, 8, 7, 2] k = 50 输出：9

所以，我们要统计乘积小于K的子序列的个数

有子问题，可以用动态规划求解

但是，为了更好地理解，我尝试写下递归代码。

注意：我得到的答案是 6，这是错误的。谁能帮帮我，如何预见正确的逻辑？

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

vector<int> A{1, 2, 3, 4};

int countSubsequence(int i, int prod, int K)
{
    if(prod > 1 && prod <= K)
        return 1;
        
    if(i >= A.size() || prod > K)
        return 0;

    return countSubsequence(i + 1, prod, K) + countSubsequence(i + 1, prod*A[i], K);
}

int main() 
{
    int K = 10;
    cout << countSubsequence(0, 1, K);
    
    return 0;
}

Answer 1

条件

    if(prod > 1 && prod <= K)
        return 1;

当从 [1, 2, 3, 4] 中选择 [1, 2] 并阻止它搜索 [1, 2, 3].[=16= 时，

将从函数（例如）中获取 return ]

还有：

条件 prod <= K 是错误的，因为您想要产品 小于 K，而不是 K 或更小 。
初始值为1时，无法区分“什么都不乘”和“只乘1”

试试这个：

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

vector<int> A{1, 2, 3, 4};

int countSubsequence(int i, int prod, int K)
{
    if(i >= A.size() && 0 <= prod && prod < K)
        return 1;
        
    if(i >= A.size() || prod >= K)
        return 0;

    return countSubsequence(i + 1, prod, K) + countSubsequence(i + 1, prod < 0 ? A[i] : prod*A[i], K);
}

int main() 
{
    int K = 10;
    cout << countSubsequence(0, -1, K);
    
    return 0;
}

计算 Product 小于 K 的所有子序列

Count All Sub sequences having Product less than K

c++

arrays

recursion

dynamic-programming