a code puzzle: missing mail

any idea for:


You are the manager of a mail room which is frequently subject to theft. A period of NN days is about to occur, such that on the iith day, the following sequence of events will occur in order:
A package with a value of V_i dollars will get delivered to the mail room (unless V_i = 0, in which case no package will get delivered).
You can choose to pay CC dollars to enter the mail room and collect all of the packages there (removing them from the room), and then leave the room
With probability SS, all packages currently in the mail room will get stolen (and therefore removed from the room).
Note that you're aware of the delivery schedule V_{1..N} , but can only observe the state of the mail room when you choose to enter it, meaning that you won't immediately be aware of whether or not packages were stolen at the end of any given day.
Your profit after the NNth day will be equal to the total value of all packages which you collected up to that point, minus the total amount of money you spent on entering the mail room.
Please determine the maximum expected profit you can achieve (in dollars).
Note: Your return value must have an absolute or relative error of at most 10^{-6}
  to be considered correct.

Constraints
1. 1 ≤ N ≤ 4,000
2. 0 ≤ Vi ≤ 1,000
3. 1≤ C ≤ 1,000
4.  0.0 ≤ S ≤ 1.0  

The DP solution is O(N^2) and can be written iteratively in bottom up form by keeping a memo[(day, value_in_mail_room)] and starting from the last day. The optimal substructure is based on everything relying on the day (and V) and the value in the mail room prior. It is possible to precompute every possible value in the mail room for all days in N^2 time by taking advantage of the fact that you need to take everything every time you enter the mail room. Then you iterate and keep the max and fill in your memo from the ground up . The main loop is for day in N: for value in possible_mail_room_values[day]: ...
possible_mail_room_values[day] is length N so the time complexity in O(N^2) total.

That being said, the iterative approach and the memoized recursive approach above both have the same time complexity. To pass the portal's test cases however you need to optimize the special case S==0 to run in O(N) time by returning max(0, sum(V) - C) early. Bit of hack. Took three days to realize lol.

brute force with cache. got 23/24 passed. the failed one hit some memory limit i guess.

1. 
   
2. from typing import List
   
3. from functools import lru_cache
   
4. # Write any import statements here
   
5. 
   
6. def getMaxExpectedProfit(N: int, V: List[int], C: int, S: float) -> float:
   
7.   # Write your code here
   
8.   sys.setrecursionlimit(8100)
   
9.   @lru_cache(None)
   
10.   def helper(day: int, value_in_mail_room: float):
    
11.     if day >= N:
    
12.       return 0
    
13.     score = 0
    
14.     if value_in_mail_room + V[day] > C:
    
15.       score = value_in_mail_room + V[day] - C + helper(day + 1, 0)      
    
16.     score = max(score, helper(day + 1, (value_in_mail_room + V[day]) * (1 - S)))
    
17.     return score
    
18.   return helper(0, 0.0)
    

复制代码

Have you solved this problem? I would like to see the solution :(