I’m working on the following problem and trying to create a dynamic programming solution that must be in O(n) time and O(1) space complexity.
The problem:
I have to find the best way to exchange between euros and dollars over n days in order to maximize my dollars.

Array $ X$ of size $ n$ . Each element represents the value of the euro on that day in dollars. So if $ X[2]$ = 20 then on the second day 1 euro is 20 dollars, 2 euros is 40 dollars, etc.

$ m$ = starting dollars (I start with 0 euros and $ m$ dollars)

$ p$ = set exchange fee for dollars>euros

$ q$ = set exchange fee for euros>dollars
So on any given day, I could choose to exchange a certain amount of money or even none at all. For example if $ X = [10, 20, 40]$ , then there are 3 days and at each day is the euro value that day in dollars. At the end I need to end up with dollars so I’ll need to exchange an even amount of times.
My ideas so far: Firstly, my inclination is that on each day we’d either want to exchange all our money or none of it. Somehow I think this would be better than only exchanging some on certain days. That way, if there is a good exchange rate, we take full advantage of it. I have no proof that this is right though.
Secondly, with my assumption above, my idea was to compute permutations of whether we exchange on certain days or not. So for example, permutations for an array of size 2 would be YN, NY, YY, NN. Y meaning we exchange, N meaning we don’t (for each day). Then, we could see which permutation yielded the max dollars. Of course, computing this for larger arrays would be terrible and not O(n) so somehow dynamic programming needs to come in.
When computing the permutations, there is repeated work and work that can be eliminated. If a permutation has an uneven number of Y’s then we can just not consider it. In terms of repeated work, take this example for an array of 4:
 YYYY
 NNNN
 YNYN
 YYNN
 NNYY
 NYNY
 YNNY
I’ve removed permutations which have uneven number of Y’s. But notice the repeated work which is in bold. The issue is, I have no idea how to make use of the fact that some work is repeated and implement this into a bottomup solution. Can anyone offer some advice? Thank you.