<p>You are given two <strong>0-indexed</strong> binary strings <code>s1</code> and <code>s2</code>, both of length <code>n</code>, and a positive integer <code>x</code>.</p>

<p>You can perform any of the following operations on the string <code>s1</code> <strong>any</strong> number of times:</p>

<ul>
	<li>Choose two indices <code>i</code> and <code>j</code>, and flip both <code>s1[i]</code> and <code>s1[j]</code>. The cost of this operation is <code>x</code>.</li>
	<li>Choose an index <code>i</code> such that <code>i &lt; n - 1</code> and flip both <code>s1[i]</code> and <code>s1[i + 1]</code>. The cost of this operation is <code>1</code>.</li>
</ul>

<p>Return <em>the <strong>minimum</strong> cost needed to make the strings </em><code>s1</code><em> and </em><code>s2</code><em> equal, or return </em><code>-1</code><em> if it is impossible.</em></p>

<p><strong>Note</strong> that flipping a character means changing it from <code>0</code> to <code>1</code> or vice-versa.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s1 = &quot;1100011000&quot;, s2 = &quot;0101001010&quot;, x = 2
<strong>Output:</strong> 4
<strong>Explanation:</strong> We can do the following operations:
- Choose i = 3 and apply the second operation. The resulting string is s1 = &quot;110<u><strong>11</strong></u>11000&quot;.
- Choose i = 4 and apply the second operation. The resulting string is s1 = &quot;1101<strong><u>00</u></strong>1000&quot;.
- Choose i = 0 and j = 8 and apply the first operation. The resulting string is s1 = &quot;<u><strong>0</strong></u>1010010<u><strong>1</strong></u>0&quot; = s2.
The total cost is 1 + 1 + 2 = 4. It can be shown that it is the minimum cost possible.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s1 = &quot;10110&quot;, s2 = &quot;00011&quot;, x = 4
<strong>Output:</strong> -1
<strong>Explanation:</strong> It is not possible to make the two strings equal.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == s1.length == s2.length</code></li>
	<li><code>1 &lt;= n, x &lt;= 500</code></li>
	<li><code>s1</code> and <code>s2</code> consist only of the characters <code>&#39;0&#39;</code> and <code>&#39;1&#39;</code>.</li>
</ul>

# The idea is that, we transform the two operation:

# flip only s[i], cost is x / 2.
# flip s[i] and s[j], cost is j - i, where i < j.
# The first operation is equal to original one,
# as long as it will be done in even times,
# and we will do a joint order(拼多多).

# We use odd to count the number of s1[i] != s2[i],
# After one operation, the odd/even of difference won't change,
# so if the number of diff is odd, we return -1.

# res is the current result,
# pre is the last time result plus the distance.
# To keep using integer, we double the cost during calculation.

# Then we iterate each pair of s1[i] and s2[i],
# we increment pre += 2, the double cost of 2nd operation.
# We update res = min(res + x, pre),
# since we can take the either operation,
# and update pre to the previous res.

# Finally, we check if we have odd diff,
# if so we return -1,
# otherwise we return res / 2, since the cost was doubled.

# class Solution:
#     def minOperations(self, s1: str, s2: str, x: int) -> int:
#         res, pre, c = 0, inf, 0
#         for a,b in zip(s1, s2):
#             pre += 2
#             if a != b:
#                 res, pre, c = min(res + x, pre), res, c ^ 1
#         return res // 2 if c == 0 else -1





# Let's look the two strings as a list of indexes that we need to fix, which we'll store in a list called diffs
# For example 1, diffs = [0, 3, 5, 8]

# Now we can either:

# move any index left or right for cost 1 (e.g. [0, 3, 5, 8] => [0, 4, 5, 8] for cost 1)
# delete any two adjacent indexes for cost 1
# delete any two non-adj indexes for cost x
# add any two non-existing indexes for cost 1, but we wouldn't ever do this
# Treat this problem like the classic house robbers DP problem.
# Start from the last element in diffs: we can either pair this with the second to last element and remove both of those for cost diffs[-1] - diffs[-2] (the distance between them), or we can take out the last element for cost x / 2. Now repeat this process until you've removed all the elements in diffs!

# Note that if there are an odd number of diffs, then it's impossible to correct them all, since every operation in the problem operates on exactly two bits. That means there must be an even number of diffs for any answer.

# Thus, for the zeroth element, if we end up there, we have to pay the x / 2, since there's nothing to pair it with, and this is how we ensure that we always fully make pairs. (we never end up paying only x / 2 -- we'll always pay the x / 2 cost an even number of times)

# The code may help you understand this. It's written in a readable way.




class Solution:
    def minOperations(self, s1: str, s2: str, x: int) -> int:
        N = len(s1)

        # list of indexes where the bits differ
        diffs = [i for i, a, b in zip(range(N), s1, s2) if a != b]
        
        # if there are an odd number of differences, it's impossible
        if len(diffs) % 2 == 1:
            return -1
        
        memo = {}

        def bestCostUpTo(i: int):
            # Returns the lowest cost to correct all diffs 
            #  up to and including diffs[i]

            if i == 0:
                return x / 2
            if i == -1:
                return 0
            if i in memo:
                return memo[i]
            memo[i] = min(
                bestCostUpTo(i - 1) + x / 2,
                bestCostUpTo(i - 2) + diffs[i] - diffs[i - 1]
            )
            return memo[i]
        
        return int(bestCostUpTo(len(diffs) - 1))
48