动态规划
数位dp
在区间[l,r]这个范围内，满足某种约束的数字的数量、总和、平方
数位dp有个通用的套路，就是先采用前缀和思想，将求解“[l,r]这个区间内的满足约束的数的数量”，转化为“[1,r]满足约束的数量 - 区间[1,l−1]满足约束的数量“
所以我们最终要求解的问题通通转化为：[1,x]中满足约束的数量，或者[0,x]中的满足约束的数量（左边界取决于题目）
typedef long long LL;
LL solve(LL x)
{
int len = 0;
while(x > 0)
{
a[++ len] = x % 10;
x /= 10;
}
return dfs(...); //记忆化搜索
}
LL dfs(int pos, bool limit, int sum)
{
if(!pos) //递归边界
return sum;
if(!limit && ~f[pos][sum]) //没限制并且dp值已搜索过
return f[pos][sum];
int up = limit ? a[pos] : 9;
LL res = 0;
for(int i = 0; i <= up; i ++)
res = (res + dfs(pos - 1, limit && i == up, sum + i)) % md;
if(!limit) //记搜，可复用
f[pos][sum] = res;
return res;
}
记忆化搜索
例子
//搜索
int f(int n){
if(n==1||n==2) return 1;
//递归边界下面马上写
if(dp[n]!=1) return dp[n];
//搜索结束后记录值
return dp[n]=f(n-1)+f(n-2);
}