分类标签归档：dp
leetcode 2376
模板题，用记忆化搜索实现会更加直观，需要知道的信息有：
1. 当前到第几位
2. 已选集合，避免重复
3. 是否到上限，到不到上限在同一位上可选范围是不一样的
4. 是否开始计数（考虑前导0）
class Solution:
def countSpecialNumbers(self, n: int) -> int:
s = str(n)
@cache
def dfs(i, mask, is_limit, is_num):
if i == len(s):
leetcode 3699
寻找子问题：如果长度为n的序列此时是递增的，它的前一个状态必须是递减的且位置n(index从1开始)的数必须大于位置为n-1的数。这时我们发现需要两个维度和两个数组定义状态，一个维度表示当前序列长度i，另一个维度表示当前结尾的数字j。一个数组dp1表示当前状态是递增时的方案数，另一个数组dp2表示当前状态是递减时的方案数。两个数组的计算方式完全对称。为简化计算，[l, r]区间可以对应到[0, r - l]。
dp1[i][j] = dp2[i - 1][0] + dp2[i - 1][1] + ... + dp2[i - 2][j - 1https://codeforces.com/problemset/problem/2078/D
有 n 对门，每对门都有左、右两个通道。初始时，左右通道各有一个人，并且这些人不能中途切换通道。
当我们通过第 i 对门的某个具体门（左或右）时：
* 如果是加法门 (+ a)：会额外产生 a 个新的人。该通道内原先存在的人数不变。
* 如果是乘法门 (x a)：假设该通道在操作前有 P 个人，操作后会变为 P * a 个人。这相当于原有的 P 个人每人变成了 a 个人中的一个“基底”，同时额外新增了 (a-1) * P 个人。
规则核心：在每一对门的操作完成后，所有在这一步新产生的