题解 | #归零#

D. 归零

知识点：动态规划/记忆化搜索

记 表示数字 的所有数位之和， 表示数字 的答案。

则有 f[i] = f[i – S(i)] + 1

初始状态：f[0] = 0

先把 以内的 预处理出来，每个询问 回答即可。

标程

C++

#include <bits/stdc++.h>

using namespace std;

constexpr int N = 1000000 + 9;

int f[N];

int sum(int x)
{
    int res = 0;
    while (x)
    {
        res += x % 10;
        x /= 10;
    }
    return res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    for (int i = 1; i < N; ++i)
    {
        f[i] = f[i - sum(i)] + 1;
    }

    int T;
    cin >> T;
    while (T--)
    {
        int n;
        cin >> n;
        cout << f[n] << '\n';
    }
}

Java

import java.util.*;
import java.io.*;

public class Main {
    static Kattio io = new Kattio();

    final static int N = 1000000 + 9;
    static int[] f = new int[N];

    static int digit_sum(int x) {
        int res = 0;
        while (x > 0) {
            res += x % 10;
            x /= 10;
        }
        return res;
    }

    public static void main(String[] args) {
        for (int i = 1; i < N; ++i) {
            f[i] = f[i - digit_sum(i)] + 1;
        }

        int q = io.nextInt();
        while (q-- > 0) {
            int x = io.nextInt();
            io.println(f[x]);
        }

        io.close();
    }
}

class Kattio extends PrintWriter {
    private BufferedReader r;
    private StringTokenizer st;
    // 标准 IO
    public Kattio() { this(System.in, System.out); }
    public Kattio(InputStream i, OutputStream o) {
        super(o);
        r = new BufferedReader(new InputStreamReader(i));
    }
    // 在没有其他输入时返回 null
    public String next() {
        try {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(r.readLine());
            return st.nextToken();
        } catch (Exception e) {}
        return null;
    }
    public int nextInt() { return Integer.parseInt(next()); }
    public double nextDouble() { return Double.parseDouble(next()); }
    public long nextLong() { return Long.parseLong(next()); }
}

Python

def digit_sum(x: int):
    res = 0
    while x:
        res += x % 10
        x //= 10
    return res

N = 10**6 + 1
dp = [0] * N
for i in range(1, N):
    dp[i] = dp[i - digit_sum(i)] + 1

q = int(input())
for _ in range(q):
    n = int(input())
    print(dp[n])