双周赛20230427

第三/四题3130. 找出所有稳定的二进制数组 II

题目大意：给定三个正整数 zero、one 和 limit，定义一个二进制数组 arr，要求满足以下条件：数组中 0 出现的次数为 zero，1 出现的次数为 one，并且数组中每个长度超过 limit 的子数组都同时包含 0 和 1。求稳定二进制数组的总数目。

实现思路：这是一个典型的动态规划问题。我们可以使用递归函数 dfs(i, j, k) 来表示以 i 个 0 和 j 个 1 开头，并且最后一个元素为 k 的稳定二进制数组的个数。其中，k 取值为 0 或 1，表示最后一个元素为 0 或 1。递归的边界条件是当 i 或 j 为 0 时，返回 1 或 0，表示当前情况下有 1 个或 0 个稳定数组。在递归过程中，我们需要考虑当前元素添加为 0 或 1 时的情况，并且根据 limit 来控制子数组的长度，避免不稳定的情况。最后，我们可以通过递归计算得到所有满足条件的稳定二进制数组的个数，并取模返回。

class Solution:
    def numberOfStableArrays(self, zero: int, one: int, limit: int) -> int:
        mod = int(1e9)+7
        @cache
        def dfs(i, j, k):
            if i==0:
                return 1 if k==1 and j<=limit else 0
            if j==0:
                return 1 if k==0 and i<=limit else 0

            if k==0:
                return ( dfs(i-1, j, 0) + dfs(i-1, j, 1) - (dfs(i-limit-1, j, 1) if i>limit else 0) ) %mod
            else:
                return ( dfs(i, j-1, 0) + dfs(i, j-1, 1) - (dfs(i, j-limit-1, 0) if j>limit else 0) ) %mod

        ans = (dfs(zero, one, 1) + dfs(zero, one, 0))%mod
        dfs.cache_clear()  # 防止爆内存  
        return ans