1529. 灯泡开关 IV
题目描述
房间中有 n
个灯泡,编号从 0
到 n-1
,自左向右排成一行。最开始的时候,所有的灯泡都是 关 着的。
请你设法使得灯泡的开关状态和 target
描述的状态一致,其中 target[i]
等于 1
第 i
个灯泡是开着的,等于 0
意味着第 i
个灯是关着的。
有一个开关可以用于翻转灯泡的状态,翻转操作定义如下:
- 选择当前配置下的任意一个灯泡(下标为
i
) - 翻转下标从
i
到n-1
的每个灯泡
翻转时,如果灯泡的状态为 0
就变为 1
,为 1
就变为 0
。
返回达成 target
描述的状态所需的 最少 翻转次数。
示例 1:
1 |
|
示例 2:
1 |
|
示例 3:
1 |
|
示例 4:
1 |
|
提示:
1 <= target.length <= 10^5
target[i] == '0'
或者target[i] == '1'
思路
动态规划
- $dp[i][0]$表示从第
i
个灯泡到末尾转换为和目标状态相同的需要的次数,$0\leq i < n$ - $dp[i][1]$表示从第
i
个灯泡到末尾转换为和目标状态相反的需要的次数,$0\leq i < n$
状态转移方程
Python代码
1 |
|
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!