题目描述
思路解析动画文字版
记住口诀:按位数分组,每组用乘法原理数个数,首位 9 种、之后每位少一个,逐组累加。下面每帧都在套它。
先搭一张表:每一行是一个「位数组」,列出首位选法、其余位选法、本组个数,最后累加成答案。我们一行行把它填满。
从最简单的 1 位数开始。0 到 9 这 10 个数,每个都只有一位数字,谈不上重复,所以全部都算。
一位数没有前导零的顾虑,这一位 0 到 9 都能填,所以首位选法填 10。
一位数后面没有别的位置,其余位这一格就写「无」,跳过它。
把首位的 10 种选法乘起来,后面没有别的位,本组个数就是 10。
累计答案从 0 起步,加上这一组的 10 个,现在累计是 10。第一行填完了。
进入两位数。关键来了:两位数的首位不能是 0,否则像 05 其实就是一位数,所以首位的选法要受限。
首位从 1 到 9 里挑,9 种选法,填 9。这就是「首位不能为 0」带来的限制。
到个位时,0 到 9 一共 10 个数字,首位已经用掉 1 个,剩下 9 个可选。注意这里个位反而可以是 0。
首位 9 种、个位 9 种,乘起来 9 乘 9 等于 81,两位数里各位不同的有 81 个。
把上一行累计的 10,加上这一组的 81,累计变成 91。这正好对上 n = 2 的答案。
进入三位数。规律和两位数一样,只是多了一位,可用的数字会再少一个。
三位数的首位同样不能是 0,1 到 9 共 9 种,填 9。
十位可填的还剩 9 个,个位又被前两位用掉两个、只剩 8 个,9 乘 8 等于 72。每多占一位,选择就少一个。
首位 9 种,乘上其余两位的 72 种,得到 648,三位数里各位不同的有 648 个。
上一行累计 91,加上这一组的 648,累计来到 739。整张表填满了。
看累计答案这一列:10、91、739。n 是几,就读到第几行的累计。n = 3 的答案就是 739。
回头看本质:首位永远是 9 种,从第二位开始,每填一位可用的数字就少一个,9、8、7 这样递减。这就是代码里那个不断乘以「越来越小的数」的来历。
顺手验证一下:如果问的是 n = 2,就读到第二行的累计 91,和题目示例完全一致。这张表一次算好,各种 n 都能查。
只有一个特例要单独记:n = 0 时范围是 0 到 1 之间,只剩数字 0 本身一个,答案直接是 1,不走上面的分组流程。
整体回放一遍:1 位数 10 个,加 2 位数 81 个到 91,再加 3 位数 648 个到 739。按位数分组、乘法原理算个数、逐组累加,这就是全部思路。
边界先想清:n = 0 返回 1;n = 1 是 10;n 超过 10 后没有新数字可填,再长的位数组都是 0,不会无限增长。
面试重点:认出「按位数累加」的 DP 结构,并知道数位 DP 框架能推广到带上界的变体。
参考代码
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 countNumbersWithUniqueDigits(self, n: int) -> int: @cache def dfs(i: int, mask: int, lead: bool) -> int: if i < 0: return 1 ans = 0 for j in range(10): if mask >> j & 1: continue if lead and j == 0: ans += dfs(i - 1, mask, True) else: ans += dfs(i - 1, mask | 1 << j, False) return ans return dfs(n - 1, 0, True)复杂度
- 时间：O(n)，组合写法只需按位数循环 n 次,每次一次乘法
- 空间：O(1)，只用累计值和当前可选数两个变量
易错点
面试追问把动画讲成自己的话
追问这题为什么被归到动态规划,明明像数学排列?
追问如果改成「各位数字都不同且小于某个具体上界 N」呢?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
最大整除子集
LeetCode 368 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题