นับซับซีเควลที่ผลคูณน้อยกว่า K ใน C++

ในบทช่วยสอนนี้ เราจะอภิบายโปรแกรมเพื่อหาจำนวนซับซีเควลที่มีผลคูณน้อยกว่า K

สำหรับเรื่องนี้ เราจะได้รับอาร์เรย์ที่ไม่มีค่าลบและค่า k งานของเราคือหาซับซีเควลทั้งหมดในอาร์เรย์ที่มีผลคูณน้อยกว่า k

ตัวอย่าง

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

// counting subsequences with product less than k
int count_sub(vector<int> &arr, int k) {
    int n = arr.size();
    int dp[k + 1][n + 1];
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= k; i++) {
        for (int j = 1; j <= n; j++) {
            dp[i][j] = dp[i][j - 1];
            if (arr[j - 1] <= i && arr[j - 1] > 0)
                dp[i][j] += dp[i / arr[j - 1]][j - 1] + 1;
        }
    }
    return dp[k][n];
}

int main() {
    vector<int> A;
    A.push_back(1);
    A.push_back(2);
    A.push_back(3);
    A.push_back(4);
    int k = 10;
    cout << count_sub(A, k) << endl;
}

เอาต์พุต

11