魔法师 (@Constanline) 在 Leetcode每日一题 —— 3129. 找出所有稳定的二进制数组 I 中发帖
思路
虽然是中等难度,但是我思考的时候真的头疼。感觉应该是我设定的概念不是那么的符合人的思维方式。
首先使用动态规划,这个比较好确定。之后往两个方向思考,
1、按位,根据这一位前面的0、1个数推断当前位可选0/1的数量(二维,但是比较难以推断,所以放弃)
2、按0/1个数,这种方式比较容易想,所以就定了这种。
状态转移方程:
dp[i][j][0] = dp[i - 1][j][0] + dp[i][j - 1][1] - dp[i - limit][j - 1][1]
dp[i][j][1] = dp[i - 1][j][0] + dp[i][j - 1][1] - dp[i - 1][j - limit][0]
先把前面一位分别是0、1的情况求和,之后如果当前位选x,那么要排除掉前一个x出现在limit位之前的。
代码
class Solution {
...