Removing Digits(Dynamic Programming)

题目描述

You are given an integer n. On each step, you may subtract one of the digits from the number.
How many steps are required to make the number equal to 0?

输入

The only input line has an integer n.
Constraints
1 ≤ n ≤ 

输出

Print one integer: the minimum number of steps.

样例输入

27

样例输出

5

提示

An optimal solution is 27 → 20 → 18 → 10 → 9 → 0.

思路分析

0→0，dp[0]=0;

1→0，dp[1]=1;

2→0，dp[2]=1;

3→0，dp[3]=1;

……

9→0，dp[9]=1;

10→9→0，dp[10]=dp[9]+1=2;

11→10→9→0，dp[11]=dp[10]+1=3;

12→10→9→0，dp[12]=dp[10]+1=3;

或12→11→10→9→0，dp[12]=dp[11]+1=4;（舍）

13→10→9→0，dp[13]=dp[10]+1=3;

或13→12→10→9→0，dp[13]=dp[12]+1=4;（舍）

……

1.初始化dp数组，大小为n+1，dp[0]=0，1~n初始化为1,000,000,000。

2.循环处理，i从1到n，i的每一位数字d，更新dp[i]=min(dp[i],dp[i-d]+1)。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1e9;
ll n;
int main(){cin>>n;vector<ll>dp(n+1,N);dp[0]=0;for(ll i=1;i<=n;i++){ll temp=i;while(temp){int d=temp%10;dp[i]=min(dp[i],dp[i-d]+1);temp/=10;}}cout<<dp[n];return 0;
}