LeetCode 2466中等动态规划
统计构造好字符串的方案数 图解题解
这道题到底在问什么
从空串出发,每步在末尾追加 zero 个字符 0,或追加 one 个字符 1,可执行任意次。若最终长度在闭区间 low 到 high 内,称为好字符串。返回不同好字符串的个数,对 10 的 9 次方加 7 取余。
- 输入
- low=3, high=3, zero=1, one=1
- 输出
- 8
- 输入
- low=2, high=3, zero=1, one=2
- 输出
- 5
最优解：一步一步想明白
- 3记牢这一句:dp[i] 是拼出长度 i 的方案数,它只由两个更短的长度转移过来,一个退回 zero 步,一个退回 one 步。这跟爬楼梯几乎一模一样,只不过一步能跨 zero 级或 one 级。下面用 low 等于 4,high 等于 8,zero 等于 2,one 等于 3 这组数据,把 dp 一格一格填出来。
- 4递推起点先把 dp 数组铺开,下标就是字符串长度,从 0 一直到 high 也就是 8。递推的地基是 dp[0] 等于 1,意思是长度 0 的空串,天然存在一种方案,就是什么都不接。绿色这格是我们唯一的已知量,后面每一格都要靠它和前面算好的格子推出来。灰色的都还没轮到。
- 5转移读取轮到长度 1。要拼出它,上一步只有两种可能:从长度 1 减 2 接一段 0 上来,或者从长度 1 减 3 接一段 1 上来。1 减 2 为负,长度不够退 2 步,不加;1 减 3 为负,长度不够退 3 步,不加。这一步两条来源都越界,没有来源格被高亮,dp[1] 直接记 0;蓝色是已经算好的,紫色是正在填的当前格。
- 6写入 dp[1]把两个来源加起来:0 加 0 等于 0,说明用步长 2 和 3 根本凑不出长度 1,方案数是 0。dp[1] 就此定格,变成蓝色加入已知,继续往右推下一格,一路都别忘了取模,防止数字撑爆。
- 7转移读取轮到长度 2。要拼出它,上一步只有两种可能:从长度 2 减 2 接一段 0 上来,或者从长度 2 减 3 接一段 1 上来。dp[2 减 2] = dp[0] = 1;2 减 3 为负,长度不够退 3 步,不加。绿色只高亮 dp[0] 这一个来源,退 3 步越界那一路不高亮也不加;蓝色是已经算好的,紫色是正在填的当前格。
- 8写入 dp[2]把两个来源加起来:1 加 0 等于 1。dp[2] 就此定格,变成蓝色加入已知,继续往右推下一格,一路都别忘了取模,防止数字撑爆。
- 9转移读取轮到长度 3。要拼出它,上一步只有两种可能:从长度 3 减 2 接一段 0 上来,或者从长度 3 减 3 接一段 1 上来。dp[3 减 2] = dp[1] = 0;dp[3 减 3] = dp[0] = 1。绿色高亮的就是这两个来源格,蓝色是已经算好的,紫色是正在填的当前格。
- 10写入 dp[3]把两个来源加起来:0 加 1 等于 1。dp[3] 就此定格,变成蓝色加入已知,继续往右推下一格,一路都别忘了取模,防止数字撑爆。
- 11转移读取轮到长度 4。要拼出它,上一步只有两种可能:从长度 4 减 2 接一段 0 上来,或者从长度 4 减 3 接一段 1 上来。dp[4 减 2] = dp[2] = 1;dp[4 减 3] = dp[1] = 0。绿色高亮的就是这两个来源格,蓝色是已经算好的,紫色是正在填的当前格。
- 12写入 dp[4]把两个来源加起来:1 加 0 等于 1。dp[4] 就此定格,变成蓝色加入已知,继续往右推下一格,一路都别忘了取模,防止数字撑爆。
- 13转移读取轮到长度 5。要拼出它,上一步只有两种可能:从长度 5 减 2 接一段 0 上来,或者从长度 5 减 3 接一段 1 上来。dp[5 减 2] = dp[3] = 1;dp[5 减 3] = dp[2] = 1。绿色高亮的就是这两个来源格,蓝色是已经算好的,紫色是正在填的当前格。
- 14写入 dp[5]把两个来源加起来:1 加 1 等于 2。dp[5] 就此定格,变成蓝色加入已知,继续往右推下一格,一路都别忘了取模,防止数字撑爆。
- 15转移读取轮到长度 6。要拼出它,上一步只有两种可能:从长度 6 减 2 接一段 0 上来,或者从长度 6 减 3 接一段 1 上来。dp[6 减 2] = dp[4] = 1;dp[6 减 3] = dp[3] = 1。绿色高亮的就是这两个来源格,蓝色是已经算好的,紫色是正在填的当前格。
- 16写入 dp[6]把两个来源加起来:1 加 1 等于 2。dp[6] 就此定格,变成蓝色加入已知,继续往右推下一格,一路都别忘了取模,防止数字撑爆。
- 17转移读取轮到长度 7。要拼出它,上一步只有两种可能:从长度 7 减 2 接一段 0 上来,或者从长度 7 减 3 接一段 1 上来。dp[7 减 2] = dp[5] = 2;dp[7 减 3] = dp[4] = 1。绿色高亮的就是这两个来源格,蓝色是已经算好的,紫色是正在填的当前格。
- 18写入 dp[7]把两个来源加起来:2 加 1 等于 3。dp[7] 就此定格,变成蓝色加入已知,继续往右推下一格,一路都别忘了取模,防止数字撑爆。
- 19转移读取轮到长度 8。要拼出它,上一步只有两种可能:从长度 8 减 2 接一段 0 上来,或者从长度 8 减 3 接一段 1 上来。dp[8 减 2] = dp[6] = 2;dp[8 减 3] = dp[5] = 2。绿色高亮的就是这两个来源格,蓝色是已经算好的,紫色是正在填的当前格。
- 20写入 dp[8]把两个来源加起来:2 加 2 等于 4。dp[8] 就此定格,变成蓝色加入已知,到这里 dp 表就填满了,下面开始统计答案。
- 21进入求和dp 从头到尾填满了,整张表是 1、0、1、1、1、2、2、3、4。注意好字符串的长度可以是 low 到 high 之间任意一个,不是只数 high。所以答案不是某一格,而是把底色框住的 low 等于 4 到 high 等于 8 这一段 dp 值全部加起来。下面从 dp[4] 开始逐格累加。
- 22区间求和把 dp[4] 等于 1 加进答案,累计变成 1。绿色是已经累进答案的那些长度,紫色是当前刚加的这一格,继续往右。
- 23区间求和把 dp[5] 等于 2 加进答案,累计变成 3。绿色是已经累进答案的那些长度,紫色是当前刚加的这一格,继续往右。
- 24区间求和把 dp[6] 等于 2 加进答案,累计变成 5。绿色是已经累进答案的那些长度,紫色是当前刚加的这一格,继续往右。
- 25区间求和把 dp[7] 等于 3 加进答案,累计变成 8。绿色是已经累进答案的那些长度,紫色是当前刚加的这一格,继续往右。
- 26区间求和把 dp[8] 等于 4 加进答案,累计变成 12。框内五格全部加完,最终答案就是 12,和整张表的区间求和结果一致。
⚠️ 容易写错的地方
✗ 错：dp[0] 初始化成 0
✓ 对：dp[0] 必须是 1
空串是所有拼法的共同起点,代表一种方案。若记 0,整条递推乘不起来,答案恒为 0
✗ 错：只把 dp[high] 当答案
✓ 对：答案是 dp 在 low 到 high 的区间和
好字符串长度可以是闭区间内任意一个,不是只要求正好等于 high,漏加中间的长度会少算
✗ 错：把 low 到 high 一整段和攒完再取模,或迟迟不取模
✓ 对：每加一次就立即对 10 的 9 次方加 7 取模
方案数增长很快。只要每步及时取模,两个已取模的数相加最多接近两倍模数,32 位也放得下;可一旦把一长段区间和先全部累计再取模,数值就会冲出范围。稳妥做法是每次累加后都及时取模,中间量用 long 承接更保险
✗ 错：算 dp[i] 时读到负下标
✓ 对：i 减 zero 或 i 减 one 为负就跳过该来源
长度不够时那条转移根本不存在,强行读负下标会越界或把不该有的方案加进来
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:
mod = 10**9 + 7
dp = [0] * (high + 1)
dp[0] = 1
ans = 0
for i in range(1, high + 1):
if i >= zero:
dp[i] += dp[i - zero]
if i >= one:
dp[i] += dp[i - one]
dp[i] %= mod
if i >= low:
ans = (ans + dp[i]) % mod
return ansC++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
const int mod = 1e9 + 7;
int countGoodStrings(int low, int high, int zero, int one) {
vector<int> dp(high + 1, 0);
dp[0] = 1;
long ans = 0;
for (int i = 1; i <= high; i++) {
long cur = 0;
if (i >= zero) cur += dp[i - zero];
if (i >= one) cur += dp[i - one];
dp[i] = cur % mod;
if (i >= low) ans = (ans + dp[i]) % mod;
}
return (int) ans;
}
};Java
import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
private static final int MOD = (int) 1e9 + 7;
public int countGoodStrings(int low, int high, int zero, int one) {
int[] dp = new int[high + 1];
dp[0] = 1;
long ans = 0;
for (int i = 1; i <= high; i++) {
long cur = 0;
if (i >= zero) {
cur += dp[i - zero];
}
if (i >= one) {
cur += dp[i - one];
}
dp[i] = (int) (cur % MOD);
if (i >= low) {
ans = (ans + dp[i]) % MOD;
}
}
return (int) ans;
}
}复杂度
时间
O(high)
长度从 0 到 high 每个值只被计算一次,每次转移只看退 zero 步和退 one 步两个来源,是常数操作;最后区间求和也是扫一遍 low 到 high。整体随 high 线性增长
空间
O(high)
只需要一个长度 high 加 1 的 dp 数组存每个长度的方案数,答案用一个变量顺手累加,不额外开销。自底向上是一遍循环,没有递归栈,空间就是这张 dp 表的 O(high)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 统计构造好字符串的方案数 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这题的核心模型是什么?+
它本质是一维计数型动态规划,和爬楼梯同构。把每一步接 zero 个 0 或 one 个 1,抽象成让长度增加 zero 或 one,于是 dp[i] 等于 dp[i 减 zero] 加 dp[i 减 one]。字符串内容不用展开,但追加 0 块和追加 1 块始终是两种不同选择,递推里的两项正好分别对应它们;即使 zero 等于 one,也要从同一个来源加两次。dp[0] 记 1,答案是 dp 在 low 到 high 的区间和。
自顶向下和自底向上有什么区别,选哪个?+
两者是同一条递推的两个方向。自底向上从 dp[0] 顺着填到 dp[high],没有递归开销,写起来直白;自顶向下从长度 0 做记忆化搜索,缓存从每个长度往后能凑的好串数,只算到得到的状态。这道题两种都能过,但 high 最大到 10 万,自顶向下递归深度会随 high 增长有爆栈风险,所以参考代码采用自底向上递推,更稳也更容易讲清填表顺序。
复杂度和取模要注意什么?+
时间和空间都是 O(high):每个长度只计算一次,转移是常数,dp 表是线性大小。取模上,方案数增长很快,关键是每步累加后都及时对 10 的 9 次方加 7 取余,别把一长段区间和攒到最后一次性取模;中间量用 long 承接更稳。下标为负的来源要跳过,别读越界。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 统计构造好字符串的方案数 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。