OP最近发布一个链接到原始问题语句，事实证明，你被允许开关灯来回。只有我下面的解决方案工作，如果你被允许只在开关灯。

OP has posted recently a link to the original problem statement, and it turned out that you are allowed to switch lights back and forth. My below solution works only if you are allowed to switch lights only on.

让我们来定义：

U [我]：=第i个光在上排

L [我]：=第i个光下排

A [1] [J]：= subconfiguration的输入配置，你有我灯在上排和j灯的下排的

例如，如果起始状态是：

For example, if the starting state is:

11101101111000101010
01111101100000010100

然后 A [5] [2] 是：

11101
01

其次，让我们定义：

Secondly, let's define:

F（I，J）：=最小的移动到关闭的开关所有的灯数A [1] [J]

您有兴趣在计算 F（N，N）

此外，让我们定义：

RU [我]：1在第i个位置结束的上排=最大连续运行

RL [我]：1的下排在第i个位置，则结束=最大连续运行

例如，如果起始状态是：

For example, if the starting state is:

11101101111000101010
01111101100000010100

然后 RU [1] = 1 ， RU [3] = 3 ， RU [4] = 0

您可以同时计算RU和RL由左到右 O（N）的时间。

You can compute both RU and RL from left to right in O(n) time.

首先，注意观察，如果 A [1] [J] 的 K_1 零点在上月底行 K_2 零点在较低的行末，那么 F（I，J）= F（I - K_1，J - K_2）因为最后 K_1 和 K_2 灯已经关闭。

First, observe that if A[i][j] has k_1 zeros at the end of the upper row and k_2 zeros at the end of the lower row, then f(i, j) = f(i - k_1, j - k_2) because the last k_1 and k_2 lights are already switched off.

注意，如果你想计算 F（I，J）有3种情况：

Observe, that if you want to compute f(i, j) there are 3 cases:

1. 关闭1的最大连续运行在上排在一个移动
2. 关闭1的下排中最大的连续运行在一个移动
3. 如果我= j和灯U [i]和L [J]接通，然后就可以关闭在一个移动交换机既有

当然，基本情况是 F（0，0），它需要0举动。

Of course, the base case is f(0, 0) and it requires 0 moves.

然后，为了计算 F（I，J）：

if U[i] is switched off: //skip zeros at the end of the upper row
   compute f(i - 1, j)
else if L[j] is switched off: //skip zeros at the end of the lower row
   compute f(i, j - 1)
else           
   if i == j // U[i] and L[j] are switched on because we skipped zeros at the end
       f(i, j) = min(f(i - RU[i], j), f(i, j - RL[j]), f(i - 1, j - 1)) + 1

   else:
       f(i, j) = min(f(i - RU[i], j), f(i, j - RL[j])) + 1

记忆化

要避免计算 F 为同一我和Ĵ在递归调用很多次，只是存储的结果已经计算 F 在哈希表和 O（1）$返回它们C $ C>，而不是重新计算。

Memoization

To avoid computing f for the same i and j many times during recursive calls, just store the results of already computed f in a hash table and return them in O(1) rather than compute again.

简单的上限，当然是为O（n ^ 2）因为有最多为O（n ^ 2）子问题。

The simple upper bound is of course O(n^2) because there are at most O(n^2) subproblems.