c++ - 计算所有乘积小于K的子序列

给定一个非负数组，找到乘积小于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;
}

最佳答案

条件

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

从[1, 2]中选择[1, 2, 3, 4]时，它将使它从函数返回，并阻止它搜索[1, 2, 3]。
也:

条件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;
}

关于c++ - 计算所有乘积小于K的子序列，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/63649222/