数位dp
lc1012
参数设计（数位DP递归函数 f ）
- i ：当前处理的数位下标（从0开始，到数字长度 m 结束），控制遍历进度。
- mask ：10位二进制数，标记已用数字（第d位为1表示数字d已用），防重复。
- is_limit ：布尔值，标记当前数位是否受 n 对应位限制（true则最多填 n 当前位数字，false可填0-9），确保不超n。
- is_num ：布尔值，标记是否已组成合法数字（false可跳过当前位，true需枚举有效数字），处理前导零。
- 记忆化 memo[i][mask] ：缓存无限制、已组成合法数字时，第i位+已用数字为mask的无重复数个数，减重复计算。
class Solution {
public:
int numDupDigitsAtMostN(int n) {
auto s = to_string(n);
int m = s.length(), memo[m][1 << 10];
memset(memo, -1, sizeof(memo)); // -1 表示没有计算过
function<int(int, int, bool, bool)> f = [&](int i, int mask, bool is_limit, bool is_num) -> int {
if (i == m)
return is_num; // is_num 为 true 表示得到了一个合法数字
if (!is_limit && is_num && memo[i][mask] != -1)
return memo[i][mask];
int res = 0;
if (!is_num) // 可以跳过当前数位
res = f(i + 1, mask, false, false);
int up = is_limit ? s[i] - '0' : 9; // 如果前面填的数字都和 n 的一样，那么这一位至多填数字 s[i]（否则就超过 n 啦）
for (int d = 1 - is_num; d <= up; ++d) // 枚举要填入的数字 d
if ((mask >> d & 1) == 0) // d 不在 mask 中
res += f(i + 1, mask | (1 << d), is_limit && d == up, true);
if (!is_limit && is_num)
memo[i][mask] = res; // 记忆化搜索
return res;
};
return n - f(0, 0, true, false);
}
};
lc1147
递归迭代的写
return 2 + longestDecomposition(s.substr(i, n - i * 2));
class Solution {
public:
int longestDecomposition(string s) {
if (s.empty())
return 0;
for (int i = 1, n = s.length(); i <= n / 2; ++i) // 枚举前后缀长度
if (s.substr(0, i) == s.substr(n - i)) // 立刻分割
return 2 + longestDecomposition(s.substr(i, n - i * 2));
return 1; // 无法分割
}
};