dp动态规划

数位dp

离谱dp，常用于有位置与位置之间的限制并计数的问题中。通过记忆化搜索求出。

代码大致模板：

const int N = 50;
//数的最高位数，可以往大点开

int s[N], tot;
//栈用来存每位的数值
int dp[N][2][2];
//状态可能还会多一些，大致与 Dfs 状态同步

inline int Dfs(int x, bool f1, bool f2){
//x 表示当前是第几位，f1 表示是否为前缀0部分，f2 表示是否为连续最高位
//后面会依题目加其他限制，视情况而定
	if(){
	//有的题目此处会有无法产生贡献的性质
		return 0;
	}
	if(!x){
	//枚举完了
		return 1;
		//此处看题目要求返回贡献值
	}
	
	if(dp[x][f1][f2] != -1){
	//记忆化
		return dp[x][f1][f2];
	}
	
	int mx = f2 ? s[x] : 9;
	//看当前位的最大取值范围，因题目而异，如十进制为 9 ，二进制为 1
	int sum = 0;
	//统计当前答案用
	
	for(int i = 0; i <= mx; ++ i){
		sum += Dfs(x - 1, f1 && (i == 0), f2 && (i == mx));
		//转移，继承状态
	}
	
	return dp[x][f1][f2] = sum;
	//记忆化
}

inline int ask(int x){
	tot= 0;
	//清空栈
	while(x){
		s[++ tot] = x % 10;
		//取最后一位
		x /= 1;
		//除去最后一位
	}
	memset(dp, -1, sizeof(dp));
	//清空 dp 数组
	return Dfs(tot, 1, 1);
	//返回答案
	//起始状态肯定满足为最大位且为前缀0位
}