題意#
給定一個整數 \( n \)，你每次操作可以將它減去「它自己任意一個位數的數字」。
舉例來說，如果現在數字是 \( 27 \)，你可以選擇減去 \( 2 \) 或減去 \( 7 \)。你的任務是計算出：最少需要操作幾次，才能把這個數字變成 \( 0 \)？
思路#
這題的核心概念就是「在所有合法的選項中，挑出走到終點步數最少的那一條路」。
我們可以建立一個長度為 \( n+1 \) 的 dp 陣列，其中 dp[i] 代表「把數字 \( i \) 扣到變成 0 的最少操作次數」。
既然要找最少次數，一開始我們把所有狀態都設成無窮大。而對於個位數字（1 到 9），我們很清楚只要把它自己扣掉一次就能變成 0，所以這些可以直接設為 1 步。
對於任意大於等於 10 的數字 \( i \)，我們可以用轉字串的技巧，把 \( i \) 拆成各個位數。然後去查表看看：如果我扣掉這個位數，剩下的數字 i - digit 還需要走幾步？
那麼 dp[i] 就是所有 dp[i - digit] + 1 裡面最小的那個值。透過由小到大的建表方式，我們就能一路推算出 dp[n] 的答案。
程式碼#
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define INF LONG_LONG_MAX/1000
#define WA() cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(), (x).end()
#define int long long
#define PII pair<int, int>
#define N 1000000+1
signed main() { WA();
// 初始化 dp 陣列，將所有值預設為無限大 (INF)
vector<int> dp(N, INF);
// 數字 1 到 9 只要減去自己（也就是只要操作 1 次）就能變成 0
for (int i = 1; i < 10; i++) dp[i] = 1;
// 由小到大推算出每個數字所需的最小步數
for (int i = 0; i < N; i++) {
// 利用 to_string(i) 把數字轉成字串，直接遍歷它的每個位數字元 c
for (auto &c : to_string(i)) {
// c - '0' 是將字元轉回對應的整數值
// dp[i] 更新為「扣除某個位數後再加 1 步」的最小值
dp[i] = min(dp[i], dp[i - (c - '0')] + 1);
}
}
int n; cin >> n;
cout << dp[n] << '\n';
}
