# preface

Review the content of the basic course of acwing algorithm. This article is to explain the basic algorithm: dynamic programming - digital statistics DP. About time complexity: bloggers are not very good at computing at present. They will make up for it in the future.

# 1, Dynamic programming

Dynamic Programming (DP) is the process of solving the optimization of the decision-making process. I personally think it is the most around of all the algorithms I have contacted at present

The solution to the problem here comes from: y total Yan's dp analysis

# 2, AcWing 338 Counting problem

Link to this question: AcWing 338. Counting problem

This blog provides screenshots of this topic:

## Analysis of this problem

Describe the purpose of the function in the code:

int count(int n, int x): returns the number of times x occurs in 1 ~ n

Int get (vector < int > num, Int l, int r): returns the number of bits from R to L in the num array

int power10(int x): returns the x power of 10

Let's look at the analysis process:

How to find the number of occurrences of i in a ~ b: Using Prefix and count(b, i) - count(a - 1, i)

Here's how to implement the count function:

Suppose we need to find the number of occurrences of 1 in 1 ~ n, n = abcdefg

Our idea is: calculate the number of occurrences of 1 in each bit respectively. Here, we assume to calculate the number of occurrences of 1 in the fourth bit, that is, 1 < = xxx1yyy < = ABCDEFG

Analyze in two general directions:

(1) xxx = 000 ~ abc - 1: in this case, the value of yyy is: 000 ~ 999, so the total number of such cases is: abc * 1000

(2) xxx = abc:

(2.1) if d < 1, then abc1yyy > abc0efg, so there is no number in line with the situation

(2.2) d = 1, the value of yyy can be 000 ~ efg, so the total number of such cases is: efg + 1

(2.3) d > 1, yyy can be 000 ~ 999, so the total number of such cases is 1000

Here's the special judgment:

In the above example, we use 1 as an example. Next, let's consider the most special number: 0

0 will not affect part (2) of the above count function implementation, but only part (1): numbers such as 0123 cannot appear

In the above case, the value range of (1) xxx should be 001 ~ abc - 1, which can prevent the occurrence of leading 0. When we traverse the number of 0 on each bit in turn, because the first cannot be 0, the for loop can be written as: for (int i = n - 1 -! X; I > = 0; I --)

## AC code

#include <iostream> #include <algorithm> #include <vector> using namespace std; const int N = 10; 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 power10(int x) { int res = 1; while (x -- ) res *= 10; return res; } int count(int n, int x) { if (!n) return 0; vector<int> num; while (n) { num.push_back(n % 10); n /= 10; } n = num.size(); int res = 0; for (int i = n - 1 - !x; i >= 0; i -- ) { if (i < n - 1) { res += get(num, n - 1, i + 1) * power10(i); if (!x) res -= power10(i); //Special judgment on 0, that is, the case of subtracting 001 } if (num[i] == x) res += get(num, i - 1, 0) + 1; else if (num[i] > x) res += power10(i); } return res; } int main() { int a, b; while (cin >> a >> b , a) { if (a > b) swap(a, b); //The data in the title is relatively small, and a > B may occur, so it needs special judgment for (int i = 0; i <= 9; i ++ ) cout << count(b, i) - count(a - 1, i) << ' '; cout << endl; } return 0; }

# 3, Time complexity

For the time complexity and proof of dynamic programming - digital statistics DP, a detailed description and proof process will be given later. At present, I'll start.