好二进制字符串的数量

Number of Good Binary Strings

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

考察：动态规划

来源：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)。