Identifications signal of dp algorithm

[qnhat2004]

When the statement like: Calculate all from 1 to n, and it has a lot of testcases.

One of the solution is, store all the calculated value from 1 to n (if n is small enough: e.g n = 2e5)

Example:
Problem: https://codeforces.com/contest/1926/problem/C
We will calculate the sum digits of all number from 1 to MAX = 2e5, store it, then with each testcase we can call the value a[n] of array

int total_digits(int n) {
    int sum = 0;
    while(n)
    {
        sum == n%10;
        n /= 10;
    }
    return sum;
}
void solve() {
    // idea: dynamic programming. We will store the sum of digits of all numbers from 1 to n, at each potition we calculate sum of current digits number and add it with sum of all number before (a[i-1])
    int MAX = 200000;
    vector<int> a(1, 0);
    for (int i = 1; i <= MAX; ++i) a.push_back(total_digits(i) + a[i-1]);
}

Important

Time for pre-cal: less than 10ms (miliseconds) = 0.01s, it's too small compared to 0.5s per test