好二进制字符串的数量

Number of Good Binary Strings

专题: Algorithmic Programming / 算法编程
难度: L3
来源: Citadel

个人笔记

题目详情

问题：好二进制字符串的数量

考察：动态规划

来源：DSA Prep / Citadel

链接：https://leetcode.com/problems/number-of-good-binary-strings

英文原题

Problem: Number of Good Binary Strings

Patterns: Dynamic Programming

Recency: 2yr

Link: https://leetcode.com/problems/number-of-good-binary-strings

Source: https://www.dsaprep.dev/blog/citadel-coding-interview-questions/

解析

思路：令 dp[len] 表示构造长度 len 的方案数。可以从 len-zero 追加一段 0，或从 len-one 追加一段 1 转移，最后累加 low 到 high 的 dp。

复杂度：时间 O(high)，空间 O(high)。

英文解析

Approach: Use DP by length. `dp[i]` counts good strings of length `i`; add from `i-zero` and `i-one` when those lengths are nonnegative, and sum counts for lengths in `[low, high]`.

Complexity: Time $O(high)$ , space $O(high)$ or rolling if only needed states are kept.