51nod 1009 数字1的数量（数位dp）

输入N(1 <= N <= 10^9)Output
输出包含1的个数Input示例
12Output示例
5转：点击打开链接一道基础的数位dp，当作入门题也挺好套用网上大多的数位dp模板，这里dp[pos]表示在没有上界的限制条件下，从pos位到最低位能组成的数一共有多少个1，简单来说，其实就是0到((10^pos) -1)有多少个1。数位dp其实就是一位一位的向下递归下去，每次枚举一位上的每一个数， 这样就可以构成一棵树，比如就21这个上界举例，dfs构成的搜索数如下图所示：dfs中的pos表示当前搜索到达第几位，num表示经过搜索树层层递归下来的路径上有几个节点数字是1，limit就是模板中的标明是否是上界的标志。关于记忆化搜索的部分，当没有limit限制的时候，就可以返回当前的保存的值，这里返回的num * ten[pos + 1] + dp[pos]值得仔细思考，其中ten[pos]表示10^pos，前一部分num*ten[pos]表示的是路径上的数字为1的节点在子树中会出现10^pos次，举例来说，假设现在已经枚举到百位之前枚举的数字是131，那么接下来的需要计算的所有数字都是131xx，(也就是从是13100~13199）100个数字，那么也就是说前面路径131中的两个1一共出现了100次，所以要乘起来；后一部分dp[pos]很好理解，就是计算在13100到13199之间的数131xx在xx部分会出现的1的数目；这样这两部分加起来就是这条路搜索的答案。代码：
#include<iostream>#include<cstdio>#include<cstring>using namespace std;const int maxn = 10;int dp[maxn], a[maxn], ten[maxn] = {1};void init(){    for(int i = 1; i < maxn; i++)        ten[i] = ten[i-1]*10;}int dfs(int pos, int num, int limit){    cnt++;    if(pos == -1) return num;    if(!limit && dp[pos] != -1) return num*ten[pos+1]+dp[pos];    int up = limit ? a[pos] : 9;    int tmp = 0;    for(int i = 0; i <= up; i++)        tmp += dfs(pos-1, num+(i==1), limit && a[pos] == i);    if(!limit) dp[pos] = tmp;    return tmp;}int solve(int x){    int pos = 0;    while(x)    {        a[pos++] = x%10;        x /= 10;    }    return dfs(pos-1, 0, 1);}int main(void){    int n;    init();    memset(dp, -1, sizeof(dp));    while(cin >> n)        PRintf("%d/n", solve(n));    return 0;}这道题的另一种数位dp的写法感觉更好一些dp[pos][num]记录的是当前长度前面有num个1的情况下1的总数
#include<iostream>#include<cstring>#include<cstdio>using namespace std;typedef long long ll;const int maxn = 20;ll dp[maxn][maxn], a[maxn];ll dfs(int pos, int num, int limit){    if(pos == -1) return num;    if(!limit && dp[pos][num] != -1) return dp[pos][num];    int up = limit ? a[pos] : 9;    ll tmp = 0;    for(int i = 0; i <= up; i++)        tmp += dfs(pos-1, num+(i==1), limit && i == a[pos]);    if(!limit) dp[pos][num] = tmp;    return tmp;}ll solve(ll x){    int pos = 0;    while(x)    {        a[pos++] = x%10;        x /= 10;    }    return dfs(pos-1, 0,  1);}int main(void){    ll n;    memset(dp, -1, sizeof(dp));    while(cin >> n)        printf("%lld/n", solve(n));    return 0;}