算法提高6.数位dp

一.数位dp简介

二.数位dp模板题

1.用递归枚举所有的数

#include <iostream> using namespace std; const int N = 15; int a[N], n; // 记录每一位的上限 // 当前填到哪一位，之前的数有没有贴着上限 int dfs(int pos, bool limit) { if(pos == 0) return 1; int up = limit ? a[pos] : 9; int ret = 0; for(int i = 0; i <= up; i++) ret += dfs(pos - 1, limit && (i == up)); return ret; }