字符串中最大的 3 位相同数字

【枚举】枚举nums中所有长度为3的字串，记录符合要求且数值最大的字串。

统计值等于子树平均值的节点数

【DFS】统计子树的节点值的和及节点数，平均数 = ⌊节点值的和 / 节点数⌋.

统计打字方案数

【分组 + 线性 DP + 乘法原理】类似爬楼梯，把相同字符分成一组，每组内仅一种字符，对于字符不是7和9的情况，定义f[i]为长为i的只有一种字符的字符串对应的文字信息种类数，将末尾1、2、3个字符单独视为一个字母，转移方程有f[i] = f[i - 1] + f[i - 2] + f[i - 3]，对于字符为7和9的情况，g[i] = g[i - 1] + g[i - 2] + g[i -3 ] + g[i -4]，不同组之间互不影响，不同组的类数相乘得到答案。

检查是否有合法括号字符串路径

【DFS】用一个变量c表示括号字符串的平衡度，遇到左括号+1，右括号-1，过程中任意时候c≥0，到终点c = 0。每次只能→↓，所以→↓的次数是固定的，路径长度也是定值，即(m - 1) + (n - 1) = 1 = m + n - 1。一开始全左括号的话，c合法的最大值为(m + n - 1) / 2 。把进入格子前c值当作格子的附加状态，定义状态(x, y, c)为进入格子(x, y)且进入前平衡度为c，一个格子的状态至多有(m + n + 1) / 2种，整个网格图至多有mn(m + n + 1) / 2种不同状态。DFS初始c= 0，进入终点前c = 1（终点必然得是右括号）。优化：左右括号数目必须相同，字符串长度（m + n + 1）需为偶数。DFS的剪枝是优点，可以降低访问到的状态数。