题目描述
思路解析动画文字版
记牢这一句:dp[i] 是拼出长度 i 的方案数,它只由两个更短的长度转移过来,一个退回 zero 步,一个退回 one 步。这跟爬楼梯几乎一模一样,只不过一步能跨 zero 级或 one 级。下面用 low 等于 4,high 等于 8,zero 等于 2,one 等于 3 这组数据,把 dp 一格一格填出来。
初始化 · dp[0] = 1(空串一种)：先把 dp 数组铺开,下标就是字符串长度,从 0 一直到 high 也就是 8。递推的地基是 dp[0] 等于 1,意思是长度 0 的空串,天然存在一种方案,就是什么都不接。绿色这格是我们唯一的已知量,后面每一格都要靠它和前面算好的格子推出来。灰色的都还没轮到。
算 dp[1] · 看两个来源：轮到长度 1。要拼出它,上一步只有两种可能:从长度 1 减 2 接一段 0 上来,或者从长度 1 减 3 接一段 1 上来。1 减 2 为负,长度不够退 2 步,不加;1 减 3 为负,长度不够退 3 步,不加。这一步两条来源都越界,没有来源格被高亮,dp[1] 直接记 0;蓝色是已经算好的,紫色是正在填的当前格。
落值 · dp[1] = 0：把两个来源加起来:0 加 0 等于 0,说明用步长 2 和 3 根本凑不出长度 1,方案数是 0。dp[1] 就此定格,变成蓝色加入已知,继续往右推下一格,一路都别忘了取模,防止数字撑爆。
算 dp[2] · 看两个来源：轮到长度 2。要拼出它,上一步只有两种可能:从长度 2 减 2 接一段 0 上来,或者从长度 2 减 3 接一段 1 上来。dp[2 减 2] = dp[0] = 1;2 减 3 为负,长度不够退 3 步,不加。绿色只高亮 dp[0] 这一个来源,退 3 步越界那一路不高亮也不加;蓝色是已经算好的,紫色是正在填的当前格。
落值 · dp[2] = 1：把两个来源加起来:1 加 0 等于 1。dp[2] 就此定格,变成蓝色加入已知,继续往右推下一格,一路都别忘了取模,防止数字撑爆。
算 dp[3] · 看两个来源：轮到长度 3。要拼出它,上一步只有两种可能:从长度 3 减 2 接一段 0 上来,或者从长度 3 减 3 接一段 1 上来。dp[3 减 2] = dp[1] = 0;dp[3 减 3] = dp[0] = 1。绿色高亮的就是这两个来源格,蓝色是已经算好的,紫色是正在填的当前格。
落值 · dp[3] = 1：把两个来源加起来:0 加 1 等于 1。dp[3] 就此定格,变成蓝色加入已知,继续往右推下一格,一路都别忘了取模,防止数字撑爆。
算 dp[4] · 看两个来源：轮到长度 4。要拼出它,上一步只有两种可能:从长度 4 减 2 接一段 0 上来,或者从长度 4 减 3 接一段 1 上来。dp[4 减 2] = dp[2] = 1;dp[4 减 3] = dp[1] = 0。绿色高亮的就是这两个来源格,蓝色是已经算好的,紫色是正在填的当前格。
落值 · dp[4] = 1：把两个来源加起来:1 加 0 等于 1。dp[4] 就此定格,变成蓝色加入已知,继续往右推下一格,一路都别忘了取模,防止数字撑爆。
算 dp[5] · 看两个来源：轮到长度 5。要拼出它,上一步只有两种可能:从长度 5 减 2 接一段 0 上来,或者从长度 5 减 3 接一段 1 上来。dp[5 减 2] = dp[3] = 1;dp[5 减 3] = dp[2] = 1。绿色高亮的就是这两个来源格,蓝色是已经算好的,紫色是正在填的当前格。
落值 · dp[5] = 2：把两个来源加起来:1 加 1 等于 2。dp[5] 就此定格,变成蓝色加入已知,继续往右推下一格,一路都别忘了取模,防止数字撑爆。
算 dp[6] · 看两个来源：轮到长度 6。要拼出它,上一步只有两种可能:从长度 6 减 2 接一段 0 上来,或者从长度 6 减 3 接一段 1 上来。dp[6 减 2] = dp[4] = 1;dp[6 减 3] = dp[3] = 1。绿色高亮的就是这两个来源格,蓝色是已经算好的,紫色是正在填的当前格。
落值 · dp[6] = 2：把两个来源加起来:1 加 1 等于 2。dp[6] 就此定格,变成蓝色加入已知,继续往右推下一格,一路都别忘了取模,防止数字撑爆。
算 dp[7] · 看两个来源：轮到长度 7。要拼出它,上一步只有两种可能:从长度 7 减 2 接一段 0 上来,或者从长度 7 减 3 接一段 1 上来。dp[7 减 2] = dp[5] = 2;dp[7 减 3] = dp[4] = 1。绿色高亮的就是这两个来源格,蓝色是已经算好的,紫色是正在填的当前格。
落值 · dp[7] = 3：把两个来源加起来:2 加 1 等于 3。dp[7] 就此定格,变成蓝色加入已知,继续往右推下一格,一路都别忘了取模,防止数字撑爆。
算 dp[8] · 看两个来源：轮到长度 8。要拼出它,上一步只有两种可能:从长度 8 减 2 接一段 0 上来,或者从长度 8 减 3 接一段 1 上来。dp[8 减 2] = dp[6] = 2;dp[8 减 3] = dp[5] = 2。绿色高亮的就是这两个来源格,蓝色是已经算好的,紫色是正在填的当前格。
落值 · dp[8] = 4：把两个来源加起来:2 加 2 等于 4。dp[8] 就此定格,变成蓝色加入已知,到这里 dp 表就填满了,下面开始统计答案。
dp 填满 · 现在框出 low 到 high 求和：dp 从头到尾填满了,整张表是 1、0、1、1、1、2、2、3、4。注意好字符串的长度可以是 low 到 high 之间任意一个,不是只数 high。所以答案不是某一格,而是把底色框住的 low 等于 4 到 high 等于 8 这一段 dp 值全部加起来。下面从 dp[4] 开始逐格累加。
累加 dp[4] = 1 · 答案到 1：把 dp[4] 等于 1 加进答案,累计变成 1。绿色是已经累进答案的那些长度,紫色是当前刚加的这一格,继续往右。
累加 dp[5] = 2 · 答案到 3：把 dp[5] 等于 2 加进答案,累计变成 3。绿色是已经累进答案的那些长度,紫色是当前刚加的这一格,继续往右。
累加 dp[6] = 2 · 答案到 5：把 dp[6] 等于 2 加进答案,累计变成 5。绿色是已经累进答案的那些长度,紫色是当前刚加的这一格,继续往右。
累加 dp[7] = 3 · 答案到 8：把 dp[7] 等于 3 加进答案,累计变成 8。绿色是已经累进答案的那些长度,紫色是当前刚加的这一格,继续往右。
累加 dp[8] = 4 · 答案到 12：把 dp[8] 等于 4 加进答案,累计变成 12。框内五格全部加完,最终答案就是 12,和整张表的区间求和结果一致。
边界想清:单点区间就取那一格 dp、zero 和 one 都等于 2 时奇数长度方案数为 0、区间和把中间的 0 也一并算上不影响结果。
面试重点:一维计数 DP 与爬楼梯同构、自顶向下与自底向上等价可互换、时间空间都是 O(high) 且每步累加后要及时取模。
参考代码
from __future__ import annotationsfrom 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 = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass 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 ans复杂度
- 时间：O(high)，长度从 0 到 high 每个值只被计算一次,每次转移只看退 zero 步和退 one 步两个来源,是常数操作;最后区间求和也是扫一遍 low 到 high。整体随 high 线性增长
- 空间：O(high)，只需要一个长度 high 加 1 的 dp 数组存每个长度的方案数,答案用一个变量顺手累加,不额外开销。自底向上是一遍循环,没有递归栈,空间就是这张 dp 表的 O(high)
易错点
面试追问把动画讲成自己的话
追问这题的核心模型是什么?
追问自顶向下和自底向上有什么区别,选哪个?
追问复杂度和取模要注意什么?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
将整数减少到零需要的最少操作数
LeetCode 2571 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题