<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>

# class Solution:
#     def minOperations(self, s1: str, s2: str, x: int) -> int:
#         diff = [ord(x1)-ord(x2) for x1, x2 in zip(s1, s2)]
#         if sum(diff) % 2 == 1: return -1
#         diff_idx = [i for i in range(len(diff)) if diff[i]]
#         def mysolution(diff_idx_):
#             n = len(diff_idx_)
#             if n == 0: return 0
#             if n == 2: return min(x, diff_idx_[1]-diff_idx_[0])
#             ans_1 = min(x, diff_idx_[1]-diff_idx_[0]) + mysolution(diff_idx_[2:])
#             ans_2 = min(x, diff_idx_[-1]-diff_idx_[0]) + mysolution(diff_idx_[1:-1])
#             return min(ans_1, ans_2)
#         return mysolution(diff_idx)
        
        








import numpy as np
class Solution:
    def minOperations(self, s1: str, s2: str, x: int) -> int:
        # operation 1 can be equal to operation 1 performing j - i times
        # if the difference bwtween s1 and s2 is odd -> impossible
        n = len(s1)
        diff = [i for i in range(n) if s1[i] != s2[i]]
        n_diff = len(diff)
        if n_diff % 2 == 1:
            return -1
        if n_diff == 0:
            return 0
        dp = np.ones((n_diff, n_diff)) * 1e6
        for i in range(n_diff-1):
            dp[i, i+1] = min(x, diff[i+1] - diff[i])
        for d in range(3, n_diff, 2):
            for i in range(n_diff - d):
                dp[i, i+d] = min(x, diff[i+d] - diff[i]) + dp[i+1, i+d-1]
                for j in range(i+1, i+d, 2):
                    dp[i, i+d] = min(dp[i, i+d], dp[i, j] + dp[j+1, i+d])
        return int(dp[0, n_diff-1])

        
        return 0


        
31300