动态规划（数位统计Dp）

数位统计Dp）"/>

动态规划（数位统计Dp）

AcWing 338. 计数问题  

思路分析：

代码展示： 

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>using namespace std;//10的x次方
int pow10(int x)
{int res = 1;while(x --) res *= 10;return res;
}
int get(vector<int> num, int l, int r)
{int res = 0;for (int i = l; i >= r; i --)res = res * 10 + num[i];return res;
}
int count(int n, int x)
{//当n == 0时if (!n) return 0;vector<int> num;//把每一位数存到数组中去while (n){num.push_back(n % 10);n /= 10;}n = num.size();int res = 0;//枚举每一位//当x为0时,因为0不会出现在最高位高位不用枚举,所以直接从第二位开始枚举for (int i = n - 1 - !x; i >= 0; i --){//第一种情况    当只有一位数时,不可能出现第一种情况if (i < n - 1){res += get(num, n - 1, i + 1) * pow10(i);//当x == 0时,x左边的位数需要从1开始枚举,但是第一种情况是从0开始枚举,所以需要处理一下细节if (x == 0) res -= pow10(i);}//第二种情况    if (x < num[i]) res += pow10(i);else if (x == num[i]) res += get(num, i - 1, 0) + 1;}return res;
}
int main()
{while (true){int a, b;cin >> a >> b;if (a == 0 && b == 0) break;if (a > b) swap(a, b);for (int i = 0; i < 10; i ++)cout << count(b, i) - count(a - 1, i) << ' ';cout << endl;}return 0;
}