作者🕵️‍♂️：让机器理解语言か

专栏🎇：算法

描述🎨：学习是一场孤独的旅行，但在算法这条路上，我会陪你越走越远！🎉

寄语💓：🐾没有白走的路，每一步都算数！🐾

目录

一、前言

二、树形DP

1、生命之树（2015年省赛，lanqiaoOJ题号131）

2、大臣的旅费（2013年第四届省赛，lanqiaoOJ题号207）

代码：

三、数位统计DP

1、例题：统计所有数码的出现个数

树形DP

• 树形DP：非线性DP，在树这种数据结构上进行的 DP
• 场景：给出一棵树，要求以最少的代价（或取得最大收益）完成给定的操作。
• 这类问题规模较大，用暴力枚举效率低无法胜任，用贪心算法不能得到最优解，因此需要用动态规划。
• 在树上做 DP 非常合适：树本身有 “子结构” 性质（树和子树），具有递归性，符合DP的性质。
• 相比线性DP，树形DP的状态转移方程更加直观。

例题一、生命之树（2015年省赛，lanqiaoOJ题号131）

【题目描述】

在 X 森林里，有一棵生命之树。每棵树的每个结点 (叶子也是结点) 上都标了一个整数，代表这个点的和谐值。要在这棵树内选出一个非空节点集 S，使得对于 S 中的任意两个点 a，b，都存在一个点列 a，v1，v2， ...，vk，b 使得这个点列中的每个点都是 S 里面的元素，且序列中相邻两个点间有一条边相连。在这个前提下，要使得 S 中的点所对应的整数的和尽量大。这个最大的和就是生命之树的评分。写一个程序来计算一棵树的分数。

【输入格式】

第一行一个整数 n 表示这棵树有 n 个结点（0

【输出格式】

输出一行一个数，表示这棵树的分数。

【输入】

5

1 -2 -3 4 5

4 2

3 1

1 2

2 5

【输出】

8 

【思路】

• 题目大意：一棵无根树，求出一个子树，使得所有结点的权值之和最大。
• 定义状态 dp[ ]：dp[i] 表示以 i 为根的子树的最大权值之和。
• 状态转移：如果子结点及其子树权值和大于零，则加入到父结点 u 的权值：dp[u] += dp[son]
• 关键：这是一棵无根树（即无环连通无向图），以任意一个结点为根做 DFS，求得的最大权值和都是一样的。

第2行设置递归深度，本题的 n 很大，递归很深。

import sys
sys.setrecursionlimit(50020)        #设置递归深度def dfs(u,fa):global ansfor son in t[u]:    # 遍历结点u的子节点if son!=fa:dfs(son,u)if dp[son]>0:    # 权值大于0dp[u]+=dp[son] # 加到父节点ans=max(ans,dp[u])n=int(input())
dp=[0] + map(int,input().split())   # 读每个点的值，并直接当成dp[]来用（不用dp[0]）
t=[[] for i in range(n+1)]          # t：tree,有点类似于邻接表；用来存边（关系）
for i in range(n-1):u,v=map(int,input().split())t[u].append(v)      # 记录邻居t[v].append(u)
ans=0
dfs(1,-1)               #或dfs(1,0)、dfs(1，n+1)。-1、0、n+1是不存在的点
print(ans)

例题二、大臣的旅费（2013年第四届省赛，lanqiaoOJ题号207）

【题目描述】

T 王国修建了大量的快速路，用于连接首都和王国内的各大城市。任何一个大城市都能从首都直接或者通过其他大城市间接到达。同时，如果不重复经过大城市，从首都到达每个大城市的方案都是唯一的。J 是 T 国大臣，巡查各大城市。J 发现，在连续行进过程中，他所花的路费与他已走过的距离有关，在走第 x 千米到第 x+1 千米这一千米中 (x是整数)，他花费的路费是 x+10。也就是说走 1 千米花费 11，走 2 千米要花费 23。J 想知道：他从某一个城市出发，中间不休息，到达另一个城市，所有可能花费的路费中最多是多少呢?

【输入格式】

第一行包含一个整数 n，表示包括首都在内的城市数 (n<=10000) 城市从 1 开始依次编号， 1 号城市为首都。接下来 n-1 行，描述 T 国的路（一定是n-1条）每行三个整数 Pi, Qi, Di，表示城市 Pi 和城市 Qi 之间有一条路，长度为 Di 千米。(Di<=1000)

【输出格式】

输出一个整数，表示大臣 J 最多花费的路费是多少。

【输入】

5

1 2 2

1 3 1

2 4 5

2 5 4

【输出】

135

【思路】

题目描述的是一棵树：有 n 个点，n-1 条边。

在这棵树上，从首都能到达其他所有城市，且方案唯一。

题目求这棵树上任意两点间的最远路径，即树的直径。

有两种做法：做两次DFS（见算法第九期——DFS(深度优先搜索）对树的应用）或两次BFS、树形DP（可用于权值为负的情况）。

【做法】

定义状态 dp[ ]：dp[u] 表示以 u 为根结点的子树上，从 u 出发能到达的最远路径长度。

路径的终点显然是 u 的一个叶子结点。

状态转移：设 u 有 t 个邻居子结点 v1, v2, ..., vt

dp[u] = max{ dp[vi] + edge(u,vi) }，1<=i<=t

• dp[ ] 和整棵树的直径长度有什么关系？

对每个结点 u，计算经过 u 的最长路径长度 f[u]。

把 u 看成树的根，u 的一个子结点是 vi

f[u] = max{dp[u]+dp[vi]+edge(u,vi)}, 1<=i<=t

• 其中 dp[u] 的计算不包括 vi 这棵子树。
• 计算出所有的 f[u] 后，整棵树的直径长度 ans 等于：ans = max{f[u]}, 1<=u<=n
• 以上步骤在一次 DFS 中完成

代码：

def dfs(u):global ansvis[u]=1for v,c in e[u]:    #u的邻居v，边长cif vis[v]==1:    continue # 已访问过dfs(v)ans=max(ans,dp[u]+dp[v]+c)dp[u]=max(dp[u],dp[v]+c)n=int(input())
e=[[] for i in range(n+1)]    #存图。邻接表
for i in range(n-1):a,b,c=map(int,input().split())e[a].append((b,c))e[b].append((a,c))
ans=0                       #答案：树的直径
vis=[0 for i in range(n+1)]
dp=[0 for i in range(n+1)]
dfs(1)
print(ans*10+ans*(ans+1)//2)    # 最长路径与费用是等差数列关系

数位统计DP

• 数位DP用于数字的数位统计。
• 例：给定一个范围 [0,k]，问区间内所有数字中，某个数码一共有多少个。
• 例如 [1, ] 中，数码 “1” 有多少个，数码 “2” 有多少个，数码 “3” 有多少个，...
• 暴力法：逐一检查每个数字，统计数码出现的次数，复杂度 O(k)
• 数位DP：一个数字的数位有个位、十位、百位、… 等等，用 DP 思想，把低位的统计结果记录下来，在高位计算时直接沿用低位的结果。复杂度仅有 O(len)，len 是 k 的位数。
• 求解区间在[a,b]数码出现的次数，则先求出区间[1,a]和[1,b]的数码出现的次数，再用区间[1,b]的数码出现的次数 - 区间[1,a]的数码出现的次数即可

例：求区间 [1，367] 内每种数码分别有多少个。

【分析】

• 定义状态 dp[ ]：dp[i] 是 i 位数的每种数码有多少个。包括0。
• 一位数 0-9，每种数码有 dp[1]=1 个。0、1、2、3、4、5、6、7、8、9。
• 二位数 00-99，每种数码有 dp[2]=20 个（100个数，每个数有2位。一共有200个数字。每个数字出现20次）。注意这里是 00-99，不是 0-99。

如果是 0-99，“0” 只出现了 11 次。这里把 “0” 和其他数字一样看待，但编程时需要特殊处理，因为按照习惯写法，数字前面的 0 应该被去掉，例如 056 应该写成 56。把这种 “0” 称为 “前导0”。前导 0 在 0-9、00-99、000-999、... 所有情况下都需要特殊处理。

• 三位数 000-999，每种数码有 dp[3] = 300 个。
• 四位数 0000~9999，每种数码有 dp[4]=4000个。

【dp[ ] 计算：排列组合】

• dp[i] = =  

排列组合的思路：从 i 个 0 递增到 i 个 9，所有的字符共出现了 次，0~9 这 10 种字符每种出现了 次。

 【dp[ ] 计算：递推】

• 递推：
• 以统计数码 “1” 的个数为例： 

1. 计算 dp[1]。即1位数字 0、1、2、...、9 中有几个 “1”，显然 dp[1]=1。
2. 计算 dp[2]。“1” 在个位上出现了 dp[i-1]×10=dp[1]×10=10次，即 01、11、21、... 、91。在十位上出现了 10^(i-1)=10^(2-1)=10次，即 10、11、12、...、19，共出现 dp[2]=20 次个 “1”。
3. 计算 dp[3]。“1” 在个位和十位上出现了 dp[2]×10=200次，即100-199的个位和十位有 dp[2] 个 "1”、200-299的个位和十位有 dp[2] 个 "1"、...、900~999 的个位和十位有 dp[2] 个 "1"。 "1" 在百位上出现了次，即100、101、...、199，共出现 dp[3]=300 个 “1”。
4. 等等。

注意点：【前导0、数位限制】

计算 [1，367] 中，每种数码一共有多少个。

• 数码有 10 种：0、1、…、9。“0” 是特殊的，需要去掉 “前导0”。
• 把 [0，367] 分成小区间：[000, 099]、[100, 199]、[200,299]、[300，367]。

（1）在这些小区间中，[000，099]、[100， 199]、[200, 299] 都可以利用 dp[2]，即 [00, 99] 的结果。最后的 [300, 367] 需要特别计算。

（2）“数位限制” 。小区间 [000, 099] 的最高位是 “0”，出现了 100 次；小区间 [100, 199] 的最高位是 “1” ，出现了 100 次；小区间 [200, 299] 的最高位是 “2"，出现了 100 次；小区间 [300, 367]的最高位是 “3”，出现了 68 次。这里的最高位，称为 “数位限制”，需要特别判断。（后两位直接套用dp来计算）

 （1）普通情况。例：00~99共出现 3 次，分别出现在 000~099、100~199、200~299 的后面 2 位上。每个数字出现了 dp[i]*n[i]=dp[2]*3=60 次。

for j in range(10):cnt[j]+=dp[i]*n[i]

(2) “数位限制”。第 3 位上的数字有 “0、1、2、3”，“3” 是最高位的数位限制。数字 “0”、"1”、"2” 分别在 000~099、100~199、200~299 的最高位上出现了 100 次，对应代码：

for j in range(n[i]):cnt[j]+=ten[i]      #特判最高位比n[i]小的数字

(2) “数位限制”。第 3 位上的数字有 “0、1、2、3”，“3” 是最高位的数位限制。数字 “0”、 "1”、 "2" 分别在 000~099、100-199、200~299 的最高位上出现了 100 次，数字 “3” 在 300~367 中出现了 68 次，对应代码：

# 数字 “3” 在 300~367 中出现了 68 次
u=0for j in range(i-1,-1,-1):u=u*10+n[j]         # u最后得到的是除去最高位的数字：67cnt[n[i]]+=u+1          # 特判最高位的数字n[i]，这里u+1是因为3在00~67（这里显示后两位）出现68次

（3）特判前导 0。在前面的计算中，都把 “0” 和其他数字一样看待，但前导 0 应该去掉。第i位有个0，对应代码：

cnt[0]-=ten[i]          #特判前导0,这里的i就是i-1的意思，因为i的范围是0~len(n)-1

例题一：统计所有数码的出现个数

【题目描述】

统计 [1, b] 范围内，每个数码的出现次数。即统计数码 0、1、2、3、4、5、6、7、8、9 的出现次数。

【输入格式】

输入一行包含一个整数 b。1<=b<=10^12。

【输出格式】

输出一行 10 个整数表示答案。

【输入样例】

93

【输出样例】

9 20 20 20 19 19 19 19 19 13

• 递推：dp[i]=dp[i-1]×10+10^(i-1)
• 排列组合：dp[i]=(i×10^i)/10=i×10^(i-1)[1，367]中，每种数码一共有多少个

def solve(x):       #计算[1,x]中每个数码的个数n = list(map(int,str(x)))    #把一个数字按位分解n=n[::-1]                   #倒过来for i in range(len(n)-1,-1,-1):     #从高到低处理x的每一位for j in range(10):cnt[j]+=dp[i]*n[i]for j in range(n[i]):cnt[j]+=ten[i]      #特判最高位比n[i]小的数字u=0for j in range(i-1,-1,-1):u=u*10+n[j]cnt[n[i]]+=u+1          #特判最高位的数字n[i]cnt[0]-=ten[i]          #特判前导0ten=[0]*15            #  ten[i]：10的i次方
ten[0]=1       
dp=[0]*15             #  i 位数的每种数码有多少个。
for i in range(1,15):   # 预计算dp[]dp[i]=i*ten[i-1]    # 使用排列组合方法；或者递推：dp[i]=dp[i-1]*10+ten[i-1]ten[i]=ten[i-1]*10
# 上面六行可以化简为以下两行
# ten = [10**i for i in range(16)]
# dp = [0] + [i*ten[i-1] for i in range(1,16)]
b=int(input())
cnt=[0]*10      #答案：cnt[i]，数字i出现了多少次
solve(b)
for i in range(10):print(cnt[i],end=' ')  #打印每个数码出现的次数