---
tags: 程式筆記
---

# [DP學習筆記1] CSES 1637 Removing Digits
> https://cses.fi/problemset/task/1637

## 題意
本題輸入為 $1$ 個正整數 $n$，我們可以透過數次（可能為0）的操作讓這個整數變成 $0$，請問最小的操作次數為何？

操作如下：考慮此數的每個位數數字，可以減去任一個位數的數字，像是：$n = 123$ 時，可以減去 $1, 2, 3$ 其中一個數字，使得 $n$ 經過一次操作之後可能為 $122, 121, 120$。

**input**
`27`
**output**
`5`

**說明**
`27 -> 20 -> 18 -> 10 -> 9 -> 0`

## 思考

**直覺：能貪心嗎？**
最一開始就想要透過貪心的方式，每次採取當前的最佳操作(local minimum)，`150 -> 145 -> 140`，但是這時候就要思考是不是貪心會使得我們喪失未來減去更大數值的操作 `150 -> 149 -> 140`，從這個例子當中我們可以看到當前的最佳策略確實喪失了未來減去更大數值的操作可行性(global minimum)。我的看法是「貪心仍然有機會，但是有風險」，所以我想換一個方法，我們將題目的思考方式告訴電腦，讓電腦自己去探索所有的可能性，這樣風險最低。

**Note**
探索所有可能性，並不是 DP(Dynamic Programming)，DP 只是幫助我們探索的時候可以減少重複性的探索，進而達到更快的探索。

**重返案發現場**
首先我們先整理題目中的線索
- 每個數字 $n$ 都有自己的最小操作次數
- $n = 0$ 的操作次數為 $0$

所以我們可以有一個結論，題目給了我們一個下階梯的方法和 1F 的定義，但是並沒有給我們一個直達 1F 的電梯，但是這個下階梯的方法只要有耐心仍然可以到達 1F。

**辦案**
當我們確立了目標與已有資源之後，我們現在可以從兩個方面來思考問題，Button-Up 與 Top-Down，什麼意思呢？

**Button-Up**(BU) 就是檢視已知線索，推理更複雜的線索。
**Top-Down**(TD) 就是檢視已知問題，推理更簡單的問題。

這兩種思考方式沒有優劣之分，只有熟練問題。

**編織過程**
有時候我覺得我的 DP 都練不起來，我想是因為我都偏向使用 TD 的思考方式，把**問題**抽絲剝繭，所以特別不擅長將**線索**編織在一起。

所以今天我想要使用編織線索的方式思考這個問題，我們已知 $n = 0$ 的操作數量為 0 ，如果想要知道 $n = x$ 的答案，只要 知道所有 $n < x$ 的答案即可，不需要知道 $n > x$ 的答案，所以我們就從最近的未知 $n = 1$ 開始，做到最遠的未知 $n = n$。

## 實作

void solve() {
	int n;
	cin >> n;
	vector<int> dp(n + 1, INT_MAX);

	dp[0] = 0;
	for(int i = 1; i <= n; i++) {
		for(int k = i; k > 0; k /= 10) if(k % 10 > 0) {
			dp[i] = min(dp[i], dp[i - k%10] + 1);
		}
	}

	cout << dp[n] << '\n';
}

**Note**
L4: 從 $n = 1$ 編織到 $n = n$，一共會有 $n+1$ 個答案。

L8: k 用途是讓我們尋找 i 的每個位數，但是這裡要注意 $-0$ 這個操作我們要避開。