Jane Street的一道DP解题

在本论坛某处看到的题目，但是在网上搜不到原题，最接近的是GeeksForGeeks，于是自己写了一下。


题目：


Given an array of integers, find the count of all subsets from the given array whose product is K.


Example:
{ 1, 1, 2, 2, 3, 4 }, target: 4, output: 8

The subsets are:
4,
1,4
1,4
1,1,4
2,2
1,2,2
1,2,2
1,1,2,2

1. </blockquote></div><div class="blockcode"><blockquote>// Bottom-up DP:
   
2. 
   
3. // The DP 2D array:
   
4. // 0 1 0 0 0
   
5. // 0 3 0 0 0
   
6. // 0 3 4 0 0
   
7. // 0 3 8 0 4
   
8. // 0 3 8 4 4
   
9. // 0 3 8 4 8
   
10. 
    
11. int Search(const std::vector<int>& nums, int target) {
    
12.     auto dp = std::vector<std::vector<int>>(nums.size(), std::vector<int>(target+1, 0));
    
13. 
    
14.     for (int i=0; i<nums.size(); ++i) {
    
15.         for (int j=1; j<target+1; ++j) {
    
16.             int count = 0;
    
17.             // +1 if the number is equal to the target.
    
18.             if (nums[i] == j) {
    
19.                 count++;
    
20.             }
    
21.             if (i>0) {
    
22.                 // If the target can be divided by the current number, we find how many subsets for target / the_current_number.
    
23.                 if (j % nums[i] == 0) {
    
24.                     count += dp[i-1][j / nums[i]];
    
25.                 }
    
26.                 // Finally, add the number of subsets without the current number.
    
27.                 count += dp[i-1][j];
    
28.             }
    
29.             dp[i][j] = count;
    
30.         }
    
31.     }
    
32.     return dp[nums.size()-1][target];
    
33. }

复制代码

1. class Solution:
   
2.     def jane_street_bottom_up(self, nums: list, target: int) -> int:
   
3.         """
   
4.              0  1  2  3  4  target
   
5.         0(1) 0  1  0  0  0
   
6.         1(1) 0  3  0  0  0
   
7.         2(2) 0  3  4  0  0
   
8.         3(0) 8  3  4  0  0
   
9.         4(3) 16 3  4  4  0
   
10.         5(4) 32 3  4  4  0
    
11.         index
    
12.         """
    
13.         table = [[0] * (target + 1) for _ in range(len(nums))]
    
14.         for i in range(len(nums)):  # target
    
15.             for j in range(target + 1):  # index start from 0
    
16.                 if nums[i] == j:
    
17.                     table[i][j] += 1
    
18.                 if i > 0:
    
19.                     table[i][j] += table[i - 1][j]  # the cases without nums[i]
    
20.                     # the cases with nums[i]
    
21.                     # two situations: 0 in the nums and target is 0
    
22.                     if nums[i] == 0:
    
23.                         if j == 0:
    
24.                             table[i][j] += 2 ** i - 1
    
25.                     else:
    
26.                         if j % nums[i] == 0:
    
27.                             table[i][j] += table[i - 1][j // nums[i]]
    
28.         # print(table)
    
29.         return table[len(nums) - 1][target]

复制代码

补充内容 (2023-07-05 23:17 +08:00):

代码片段仅仅加了一些可能性，即当target可能是0或数组中也可能有0的情况。相当于增加了一点cornor case。例如：nums = [1,1,2,0,3,4], target = 0.则可返回32。这个边缘情况也可以放置在主要代码片段外面，专门写出来。

这题有个细节，有没有0存在的可能性？

背包問題啊

leetcode上面这种背包题目很多，各种变形题

Javery 发表于 2023-07-04 20:36:06
这题有个细节，有没有0存在的可能性？

子集，不是货物无限的背包问题

确实是背包， dp[len][target+1] 行吗？
题里没说ary大小，也没说target大小。1e9的target能做吗，如果用除法呢？

Javery 发表于 2023-7-4 21:21
补充内容 (2023-07-05 23:17 +08:00):

代码片段仅仅加了一些可能性，即当target可 ...

数组中有0还需要考虑吗

想问一下既然是subset，暴力backtracking是不是也可以，就是复杂度有点高