https://pic.leetcode-cn.com/1651749663-mqoNLx-%E5%B1%8F%E5%B9%95%E6%88%AA%E5%9B%BE%202022-05-05%20192055.png
题目网址https://leetcode-cn.com/problems/subarray-product-less-than-k/
源码如下:
int sum=0;
int cx=1;
int best=1;
class Solution {
public:
void dfs(int t, int m, vector<int>& nums, int M)
{
if (t >= m)
{
sum++;
best = cx;
return;
}
if (cx * nums[t] < M)
{
cx *= nums[t];
dfs(t + 1, m, nums, M);
cx /= nums[t];
}
if (bound(t + 1, m, nums, M) < M)
{
dfs(t + 1, m, nums, M);
}
}
int bound(int i, int m, vector<int>& nums, int M)
{
int rx = 1;
while (i < m)
{
rx *= nums[i];
i++;
}
return cx * rx;
}
int numSubarrayProductLessThanK(vector<int>& nums, int k) {
int m=nums.size();
dfs(0,m,nums,k);
return sum;
}
};