Class Solution

DP/SubarrayProductLessThanK.py:26–63

可剪枝优化。
"""
class Solution(object):
    def numSubarrayProductLessThanK(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        
        dp = []
        result = 0
        start = 0
        for i in range(len(nums)):
            if nums[i] < k:
                result += 1
                dp = [nums[i]]
                start = i
                break
        
        for i in range(start+1, len(nums)):
            if nums[i] == 1 and nums[i] < k:
                dp.append(1)
                result += len(dp)
                continue
                
            new = []
            
            if nums[i] < k:
                result += 1
                new.append(nums[i])
                
            
            for j in dp:
                if j * nums[i] < k:
                    result += 1
                    new.append(j * nums[i])
            
            dp = new
        return result