The dynamic programming task in Python

Question

Here is a toy version of the DP problem that I am trying to solve. Let's say that we have two neighborhoods with 2 and 3 parking lots, respectively.

• Each parking lot has a capacity that ranges from 0 to a fixed positive number.
• The state of the system at any time is the available parking places for stations. For example, (2, 3, 4, 5, 6), where (2, 3) refer to available places of stations in the first neighborhood and (4, 5, 6) in the second neighborhood.
• Each station can be turned on (1) or off (0), and we want to find which stations to turn on or off in each state. To this, we must check all possible on / off combinations. One such combination for the aforementioned parameter would be [[0,1], [1,0,1]].
• Finally, there are positive probabilities of movement from each station in the vicinity of the departure to the destination area. For example, λ_ {1,2} ^ {2} is the probability of a transition from station 2 in neighborhood 1 to neighborhood 2.

I need help on how I should store the above things to make life easier and how to encode state value calculations. The states that you can move from the current state are determined by the lambda probabilities and this recommendation. For example, for state (2, 3, 4, 5, 6) and recommendations [[0,1], [1,0,1]], the value will be:

• Explanation of the first term: given this lambda, we get that the car leaves station 1 in neighborhood 1 to go to the next two. Consequently, the state of station 1 in neighborhood 1 goes from 2 to 3. In addition, we have two recommended stations in neighborhood 2 where the car can go equally. Therefore, we get two members. First, the throughput of station 1 in neighborhood 2 drops by 1, and in the second term, the power of station 3 in neighborhood 2 drops by 1.
  • A similar explanation for the second term, with the only difference being that the car is now leaving station 2 in neighborhood 1.
  • For the third term from lambda it can be seen that the car goes from station 1 in neighborhood 2 to neighborhood 1. But now only the second station of neighborhood 1 is recommended, and therefore we get only one term in which the capacity of station 2 in neighborhood 1 drops by 1, and Station 1 in neighborhood 2 increases by 1.
  • Similar explanations for other conditions.

The general pseudo-code of the problem that I have in mind:

Create State_Space Create recommendation_combinations # All possible (0,1) combinations V = dict([state,0] for state in State_Space) # Initialize the value vector for each_state in State_Space: for each_recommendation_combination in recommendation_combinations: Compute V(state)_combination V(state) = min(V(state)_combination) 

Given the complexity of the structure of the problem (i.e., the stations inside the neighborhoods), how would you recommend keeping it higher? (I thought of using dictionaries, but I don’t know how to use itertools with dictionaries to create combinations of recommendations). Moreover, any programming help to calculate state values ​​is much appreciated!

Thank you very much in advance.