字符串中最大的 3 位相同數(shù)字

【枚舉】枚舉nums中所有長度為3的字串，記錄符合要求且數(shù)值最大的字串。

統(tǒng)計(jì)值等于子樹平均值的節(jié)點(diǎn)數(shù)

【DFS】統(tǒng)計(jì)子樹的節(jié)點(diǎn)值的和及節(jié)點(diǎn)數(shù)，平均數(shù) = ?節(jié)點(diǎn)值的和 / 節(jié)點(diǎn)數(shù)?.

統(tǒng)計(jì)打字方案數(shù)

【分組 + 線性 DP + 乘法原理】類似爬樓梯，把相同字符分成一組，每組內(nèi)僅一種字符，對于字符不是7和9的情況，定義f[i]為長為i的只有一種字符的字符串對應(yīng)的文字信息種類數(shù)，將末尾1、2、3個(gè)字符單獨(dú)視為一個(gè)字母，轉(zhuǎn)移方程有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]，不同組之間互不影響，不同組的類數(shù)相乘得到答案。

檢查是否有合法括號字符串路徑

【DFS】用一個(gè)變量c表示括號字符串的平衡度，遇到左括號+1，右括號-1，過程中任意時(shí)候c≥0，到終點(diǎn)c = 0。每次只能→↓，所以→↓的次數(shù)是固定的，路徑長度也是定值，即(m - 1) + (n - 1) = 1 = m + n - 1。一開始全左括號的話，c合法的最大值為(m + n - 1) / 2 。把進(jìn)入格子前c值當(dāng)作格子的附加狀態(tài)，定義狀態(tài)(x, y, c)為進(jìn)入格子(x, y)且進(jìn)入前平衡度為c，一個(gè)格子的狀態(tài)至多有(m + n + 1) / 2種，整個(gè)網(wǎng)格圖至多有mn(m + n + 1) / 2種不同狀態(tài)。DFS初始c= 0，進(jìn)入終點(diǎn)前c = 1（終點(diǎn)必然得是右括號）。優(yōu)化：左右括號數(shù)目必須相同，字符串長度（m + n + 1）需為偶數(shù)。DFS的剪枝是優(yōu)點(diǎn)，可以降低訪問到的狀態(tài)數(shù)。